使用子線性時間在1百萬<string name，int score> pairs中搜索

Question

我有一個包含100萬對的JSON對象。

var student = {[ 
    { 
     name: "govi", 
     score: "65" 
    }, 
    { 
     name: "dharti", 
     score: "80" 
    }, 
    { 
     name: "Akash", 
     score: "75" 
    },............. till 1 million 
    ] 
}; 

現在我的關注如下。

我想建立一個服務器程序，它接受一個用戶查詢，以便對於每個查詢，它將響應前10名（按分數排序），以s開頭或包含'_s'（例如， 「收入」和「annual_revenue」匹配前綴「rev」）。對於普通的Jquery和json程序來說太簡單了，但是有一個條件。

條件

查詢應答應子線性時間運行（在名稱的輸入的數量）。

Answer 1

1）從的NuGet代表

2添加Newtonsoft庫）添加以下引用

using Newtonsoft.Json; 
using Newtonsoft.Json.Linq; 

3）使用此代碼

//JObjectString is your string that contains the values 
      JArray ValuesArray = JArray.Parse(JObjectString); 

      Dictionary<string, int> SearchDict = new Dictionary<string, int>(); 

      //here the search term is the query from the user input 
      string searchTerm = "govi"; 

      foreach (var rec in ValuesArray) 
      { 
       SearchDict.Add(rec["name"].ToString(), Int32.Parse(rec["score"].ToString())); 
      } 
      //here is the result in javascript array format, return it 
      string ResultString = JsonConvert.SerializeObject(SearchDict.Where(o => o.Key == searchTerm | o.Key.Contains(searchTerm)). 
       Select(o => o).OrderByDescending(o => o.Value).Take(10).Select(o => o)); 

Answer 2

1. 排序的陣列降按分數。這確保下一步創建已經排序的子集，並且比排序（經常重疊）的子集更快。

2. 通過字符創建一本字典。遍歷每個名​​稱的每個字符並將該項添加到子集中。

3. 當搜索一個子字符串（比如「rev」）時，可以檢查每個字母的數組，可以選擇最短的字符串，而不是整個數據。

一個例子：

//building the map 
let map = Object.create(null); 
data 
    //.slice() /if you can't rearrange the items in the original Array 
    .sort((a,b) => b.score - a.score) 
    .forEach(item => { 
     for(let char of new Set(item.name)){ 
      var arr = map[char] ||| (map[char] = []); 
      arr.push(item); 
     } 
    }); 

function findSubset(str){ 
    let best; 
    for(let char of new Set(str)){ 
     //there can be no entry for "rev", if there is no subset for "v" for example 
     if(!(char in map)) return []; 

     let arr = map[char]; 
     if(!best || arr.length < best.length) 
      best = arr; 
    } 
    return best || []; 
} 

function contains(str, limit=Infinity){ 
    let subset = findSubset(str); 
    let results = []; 
    for(let i=0; i<subset.length && results.length < limit; ++i){ 
     let item = subset[i]; 
     if(item.name.includes(str)) 
      results.push(item); 
    } 
    return results; 
} 

Answer 3

調用StudentIndex.GetTop10（字符串s）將是O（n），其中由n是串s的長度。這會消耗大量的內存，但有很多方法可以減少這種情況。 （例如，一旦Node.Top10具有少於10個值，執行線性搜索）。

我給你寫樹建築。

public class Student 
    { 
     public string Name { get; set; } 
     public double Score { get; set; } 
    } 
    public class Node 
    { 
     public Dictionary<char, Node> Children { get; set; } 
     public List<Student> Top10 { get; set; } 
    } 
    public class StudentIndex 
    { 
     private Node _root; 

     public StudentIndex(IEnumerable<Student> students) 
     { 
      Node root = new Node(); 

      foreach(var student in students) 
      { 
       var parts = student.Name.Split(new[] {'_'}); 
       foreach(var part in parts) 
       { 
        //you'll add each student to the tree using each part of the name  
       } 
      } 
      //set _root 
     } 

     public IEnumerable<Student> GetTop10(string s) 
     { 
      return GetTop10(s.ToLower(), _root); 
     } 

     private IEnumerable<Student> GetTop10(string s, Node node) 
     { 
      if (node.Children == null) return node.Top10; 
      if (s.Length == 0) return node.Top10; 

      var c = s[0]; 
      Node n; 
      if (node.Children.TryGetValue(c, out n)) 
      { 
       return GetTop10(s.Substring(1), n); 
      } 
      else 
      { 
       return Enumerable.Empty<Student>(); 
      } 
     } 
    }