Mam dużą gamę słów w JavaScript (~ 100.000) i chciałbym szybko zwrócić ich podzbiór na podstawie wzoru tekstowego.

Na przykład, chciałbym zwrócić wszystkie słowa, które zaczynają się od wzoru, więc wpisując {x0}} powinien dać mi ["happy", "happiness", "happening", etc, etc].

Jeśli to możliwe, chciałbym zrobić to bez iteracji przez całą tablicę.

Coś takiego nie działa wystarczająco szybko:

// data contains an array of beginnings of words e.g. 'hap'
$.each(data, function(key, possibleWord) {
 found = $.inArray(possibleWord, words);
 // do something if found
}

Wszelkie pomysły na temat tego, jak mogłem szybko zmniejszyć zestaw do możliwych meczów bez iteracji na całym zestawie słów? Tablica słów jest w porządku alfabetycznym, jeśli to pomoże.

2
standardnerds 19 listopad 2011, 03:42

6 odpowiedzi

Najlepsza odpowiedź

Jeśli chcesz wyszukać prefiksy, istnieją struktury danych tylko dla tego, takie jak Trie i therary search

Szybki Wyszukiwanie Google i niektóre promienie JavaScrit Trie i Autouzupełnione implementacje pojawiają się:

http://ejohn.org/blog/javascript-rie-performance-analization/

Autouzupełnianie za pomocą trie

http://odhyan.com/blog/2010/11/trie-implementation-in-javascript/

3
Community 23 maj 2017, 12:29

Nie mam absolutnie nie mam pojęcia, czy jest to jakikolwiek szybciej (a Test JSPerf prawdopodobnie w porządku .. .), ale możesz to zrobić z jednym gigantycznym ciągiem i wyszukiwaną regexp zamiast tablic:

var giantStringOfWords = giantArrayOfWords.join(' ');
function searchForBeginning(beginning, str) {
    var pattern = new RegExp('\\b' + str + '\\w*'),
        matches = str.match(pattern);
    return matches;
}

var hapResults = searchForBeginning('hap', giantStringOfWords);
1
sdleihssirhc 18 listopad 2011, 23:56

Najlepszym podejściem jest lepsze struktura danych. Zrób obiekt z kluczami jak "HAP". Ten członek posiada tablicę słów (lub przyrostek słów, jeśli chcesz zaoszczędzić miejsce) lub oddzielny ciąg słów do wyszukiwania regexp.

Oznacza to, że będziesz miał krótsze przedmioty do itera / wyszukiwania. Innym sposobem jest posortowanie tablic i użyć wzoru wyszukiwania binarnego. Jest tu dobra rozmowa o technikach i optymalizacji: http://ejohn.org/blog/ Poprawione-javascript-słownik-search /

0
AutoSponge 18 listopad 2011, 23:50

Przypuszczam, że używanie Surowego JavaScript może trochę pomóc, możesz zrobić:

var arr = ["happy", "happiness", "nothere", "notHereEither", "happening"], subset = [];
for(var i = 0, len = arr.length; i < len; i ++) {
     if(arr[i].search("hap") !== -1) {
           subset.push(arr[i]);
     }
}
//subset === ["happy", "happiness","happening"]

Ponadto, jeśli tablica zostanie zamówiona, możesz wcześnie złamać, jeśli pierwsza litera jest większa niż pierwsza z wyszukiwania, zamiast zapętlić całą tablicę.

0
nicosantangelo 18 listopad 2011, 23:50
var data = ['foo', 'happy', 'happiness', 'foohap'];    
jQuery.each(data, function(i, item) {
      if(item.match(/^hap/))
        console.log(item) 
    });

Jeśli masz dane w tablicy, będziesz musiał pętli przez całą rzecz.

0
Jordan Brown 18 listopad 2011, 23:52

Naprawdę prosta optymalizacja jest na obciążeniu strony Przejdź przez duże słowa macierzy i zanotuj, jakie zakresy wskaźników dotyczą każdej litery wyjściowej. Np. W moim przykładzie poniżej "A" słów przechodzą od 0 do 2, słowa "B" przechodzą od 3 do 4 itp. W rzeczywistości faktycznie wykonując mecz wzorcowy, przejrzyj jedynie odpowiedni zakres. Chociaż oczywiście niektóre litery będą miały więcej słów niż inne, dane wyszukiwanie będzie musiało przejrzeć średnio 100 000/26 słów.

// words array assumed to be lowercase and in alphabetical order
var words = ["a","an","and","be","blue","cast","etc."];

// figure out the index for the first and last word starting with
// each letter of the alphabet, so that later searches can use
// just the appropriate range instead of searching the whole array
var letterIndexes = {},
    i,
    l,
    letterIndex = 0,
    firstLetter;
for (i=0, l=words.length; i<l; i++) {
    if (words[i].charAt(0) === firstLetter)
       continue;
    if (firstLetter)
        letterIndexes[firstLetter] = {first : letterIndex, last : i-1};
    letterIndex = i;
    firstLetter = words[i].charAt(0);
}

function getSubset(pattern) {
    pattern = pattern.toLowerCase()
    var subset = [],
        fl = pattern.charAt(0),
        matched = false;
    if (letterIndexes[firstLetter])
        for (var i = letterIndexes[fl].first, l = letterIndex[fl].last; i <= l; i++) {
            if (pattern === words[i].substr(0, pattern.length)) {
                subset.push(words[i]);
                matched = true;
            } else if (matched) {
                break;
            }
        }
    return subset;        
}

Należy również pamiętać, że podczas wyszukiwania wraz z tablicą (zakres w ramach), po znalezieniu meczu ustawiam flagę, która wskazuje, że przeszliśmy przez wszystkie słowa, które są alfabetycznie przed wzorem i teraz przechodzą przez pasujące słowa. W ten sposób, gdy tylko wzór nie pasuje już, możemy wyrwać się z pętli. Jeśli wzór nie pasuje do WSZYSTKICH, nadal kończymy się przez wszystkie słowa dla tego pierwszego listu.

Ponadto, jeśli robisz to jako typy użytkowników, gdy litery są dodawane do końca wzoru, musisz przeszukać tylko poprzedni podzbiór, a nie przez całą listę.

Str.s. Oczywiście, jeśli chcesz przerwać listę słów przez pierwszą literę, możesz łatwo zrobić tę stronę serwera.

0
nnnnnn 19 listopad 2011, 01:58