Szybko znajdź, czy wartość jest obecna w tablicy C?

Jest sztuczka na optymalizację (zapytano mnie kiedyś o to na rozmowie kwalifikacyjnej):

• jeśli ostatni wpis w tablicy zawiera szukaną wartość, zwróć true
• Zapisz szukaną wartość do ostatniego wpisu w tablicy
• iteracja tablicy, dopóki nie napotkasz wartości, której szukasz
• jeśli napotkałeś go przed ostatnim wpisem w tablicy, zwróć true
• Return false

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Daje to jedną gałąź na iterację zamiast dwóch gałęzi na iterację.

UPDATE:

Jeśli możesz przydzielić tablicę do SIZE+1, możesz pozbyć się części" last entry swapping":

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

Możesz również pozbyć się dodatkowej arytmetyki osadzonej w theArray[i], używając zamiast tego:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Jeśli kompilator jeszcze go nie zastosuje, to ta funkcja zrobi to na pewno. Z drugiej strony ręcznie, może to utrudnić optymalizatorowi rozwinięcie pętli, więc będziesz musiał to sprawdzić w wygenerowanym kodzie złożenia...

Prosisz o pomoc w optymalizacji algorytmu, który może popchnąć cię do asemblera. Ale twój algorytm (wyszukiwanie liniowe) nie jest tak sprytny, więc powinieneś rozważyć zmianę algorytmu. Np.:

• doskonała funkcja hash
• wyszukiwanie binarne

Doskonała funkcja hash

Jeśli twoje 256 "poprawnych" wartości są statyczne i znane w czasie kompilacji, możesz użyć perfect hash function . Musisz znaleźć funkcję hash to mapuje wartość wejściową do wartości z zakresu 0..n, gdzie nie ma kolizji dla wszystkich ważnych wartości, na których Ci zależy. Oznacza to, że nie ma dwóch" poprawnych " wartości do tej samej wartości wyjściowej. Szukając dobrej funkcji hash, dążysz do:

• Zachowaj funkcję hash dość szybko.
• n . Najmniejszy można uzyskać 256 (minimal perfect hash function) , ale to prawdopodobnie trudne do osiągnięcia, w zależności od data.

Uwaga dla efektywnych funkcji hashowych, N jest często potęgą 2, która jest równoważna bitowej masce niskich bitów (i operacji). Przykładowe funkcje hash:

• CRC bajtów wejściowych, modulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n (wybierając tyle i, j, k, ... w razie potrzeby, z przesunięciem w lewo lub w prawo)

Następnie tworzy się stałą tabelę N wpisów, gdzie hash mapuje wartości wejściowe do indeksu i do tabeli. Na poprawne wartości, wpis tabeli i zawiera poprawną wartość. Dla wszystkich pozostałych pozycji tabeli, upewnij się, że każda pozycja indeksu i zawiera inną nieprawidłową wartość, która nie ma hashu i.

Następnie w rutynie przerwania, z wejściem x :

1. Hash x do indeksu i (który mieści się w zakresie 0..n)
2. poszukaj pozycji i w tabeli i sprawdź, czy zawiera ona wartość x .

To będzie być znacznie szybsze niż wyszukiwanie liniowe 256 lub 1024 wartości.

Napisałem Kod Pythona , aby znaleźć sensowne funkcje hashujące.

Wyszukiwanie binarne

Jeśli posortujesz tablicę 256 "poprawnych" wartości, możesz wykonać wyszukiwanie binarne , zamiast wyszukiwania liniowego. Oznacza to, że powinieneś być w stanie przeszukiwać tabelę 256 wpisów tylko w 8 krokach (log2(256)) lub tabelę 1024 wpisów w 10 krokach. Ponownie, będzie to znacznie szybsze niż wyszukiwanie liniowe 256 lub 1024 wartości.

Zachowaj tabelę w uporządkowanej kolejności i użyj rozwiniętego wyszukiwania binarnego Bentleya:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

Chodzi o to,

• jeśli wiesz, jak duży jest stół, to wiesz, ile będzie iteracji, więc możesz go w pełni rozwinąć.
• nie ma sensu testować przypadku == na każdej iteracji, ponieważ, z wyjątkiem ostatniej iteracji, prawdopodobieństwo wystąpienia tego przypadku jest zbyt niskie, aby uzasadnić poświęcenie czasu na testowanie.**
• na koniec rozszerzając tabelę do moc 2, dodajesz co najwyżej jedno porównanie, a co najwyżej dwa współczynniki pamięci.

* * Jeśli nie jesteś przyzwyczajony do myślenia w kategoriach prawdopodobieństwa, każdy punkt decyzyjny ma entropię }, która jest średnią informacją, której nauczysz się wykonując ją. Dla testów >= prawdopodobieństwo każdej gałęzi wynosi około 0,5, A-log2(0,5) wynosi 1, więc jeśli weźmiesz jedną gałąź uczysz się 1 bit, a jeśli weźmiesz drugą gałąź uczysz się 1 bit, a średnia jest tylko sumą to, czego nauczysz się na każdej gałęzi, zwiększa prawdopodobieństwo tej gałęzi. Więc 1*0.5 + 1*0.5 = 1, więc Entropia testu >= wynosi 1. Ponieważ masz 10 bitów do nauki, potrzeba 10 gałęzi. Dlatego jest szybki!

Z drugiej strony, co jeśli twój pierwszy test to if (key == a[i+512)? Prawdopodobieństwo prawdziwości wynosi 1/1024, podczas gdy prawdopodobieństwo fałszu wynosi 1023/1024. Więc jeśli to prawda, uczysz się wszystkich 10 bitów! Ale jeśli to fałsz to się uczysz-log2(1023/1024) = .00141 bity, praktycznie nic! Więc średnia kwota, którą się uczysz z tego testu pochodzą 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 bity. Około setnej części. Ten test nie ma swojego ciężaru!

Jeśli zbiór stałych w Twojej tabeli jest znany z góry, możesz użyć perfect hashing , aby upewnić się, że tylko jeden dostęp jest do tabeli. Doskonałe hashowanie określa funkcję hash to mapuje każdy interesujący klucz do unikalnego gniazda (ta tabela nie zawsze jest gęsta, ale możesz zdecydować, na jaką gęstą tabelę możesz sobie pozwolić, z mniej gęstymi tabelami Zwykle prowadzącymi do prostszych funkcji haszujących).

Zazwyczaj idealną funkcją skrótu dla określonego zestawu kluczy jest stosunkowo łatwe do obliczenia; nie chcesz, aby to było długie i skomplikowane, ponieważ konkuruje to o czas, być może lepiej spędzony na robieniu wielu sond.

Perfect hashing to schemat "1-probe max". Można uogólnić ten pomysł, myśląc, że należy wymienić prostotę przetwarzania kodu hashowego z czasem potrzebnym na wykonanie sond K. W końcu celem jest "najmniej całkowity czas, aby spojrzeć w górę", a nie najmniej sond lub najprostsza funkcja skrótu. Jednak nigdy nie widziałem, żeby ktoś budował k-sondy-algorytm haszujący max. Podejrzewam, że można to zrobić, ale to prawdopodobnie badania.

Jeszcze jedna myśl: jeśli twój procesor jest bardzo szybki, to jeden sonda do pamięci z idealnego hasha prawdopodobnie dominuje nad czasem wykonania. Jeśli procesor nie jest bardzo szybki, to sondy k > 1 mogą być praktyczne.

Użyj zestawu skrótów. Da o(1) Czas wyszukiwania.

Poniższy kod zakłada, że możesz zarezerwować wartość 0 jako wartość "pustą", tzn. nie występującą w rzeczywistych danych. Rozwiązanie można rozszerzyć w sytuacji, w której tak nie jest.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

W tej przykładowej implementacji, czas wyszukiwania będzie zazwyczaj bardzo niski, ale w najgorszym przypadku może wynosić do liczby zapisanych wpisów. W przypadku aplikacji w czasie rzeczywistym można rozważyć również implementację wykorzystującą binarne drzewa, które będą miały bardziej przewidywalny czas wyszukiwania.

W tym przypadku warto zbadać filtry Bloom. Są w stanie szybko ustalić, że wartość nie jest obecna, co jest dobrą rzeczą, ponieważ większość możliwych wartości 2^32 nie znajduje się w tablicy 1024 elementów. Istnieje jednak kilka fałszywych alarmów, które wymagają dodatkowego sprawdzenia.

Ponieważ twoja tabela jest pozornie statyczna, możesz określić, które fałszywie dodatnie istnieją dla Twojego filtra Bloom i umieścić je w idealnym hash.

Zakładając, że Twój procesor pracuje z częstotliwością 204 MHz, co wydaje się być maksimum dla lpc4357, a także zakładając, że wynik pomiaru czasu odzwierciedla średnią wielkość (połowę przejechanej tablicy), otrzymujemy:

• Częstotliwość procesora: 204 MHz
• okres cyklu: 4,9 NS
• Czas trwania w cyklach: 12,5 µs / 4,9 NS = 2551 cykli
• cykle na iterację: 2551 / 128 = 19,9

Więc twoja pętla wyszukiwania spędza około 20 cykli na iterację. To nie brzmi okropnie, ale myślę, że aby zrobić to szybciej, musisz spojrzeć na montaż.

Zalecałbym opuszczenie indeksu i użycie porównania wskaźników, a następnie wykonanie wszystkich wskaźników const.

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

Inne osoby sugerowały reorganizację tabeli, dodanie wartości sentinel na końcu lub sortowanie jej w celu zapewnienia wyszukiwania binarnego.

Piszesz: "używam również arytmetyki wskaźnika i pętli for, która wykonuje zliczanie w dół zamiast w górę (sprawdzanie czy i != 0 jest szybsze niż sprawdzanie czy i < 256)."

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

Wydaje się byćidiomatyczne dla kompilatora. Pętla jest idiomatyczne, a indeksowanie tablicy nad zmienną pętli jest idiomatyczne. Żonglowanie arytmetyką wskaźnikową i wskaźnikami ma tendencję do zaciemniania idiomów kompilatora i generowania kodu związanego z tym, conapisałeś , a nie tym, co pisarz kompilatora zdecydował się być najlepszym kursem dla ogólnegozadania .

Na przykład powyższy kod może być skompilowany w pętlę biegnącą od -256 lub -255 do zera, indeksując się &the_array[256]. Prawdopodobnie rzeczy, które są nawet nie jest możliwe wyrażenie w poprawnym C, ale pasuje do architektury maszyny, dla której generujesz.

Więc nie rób mikrooptymalizacji. Po prostu wrzucasz Klucze do pracy swojego optymalizatora. Jeśli chcesz być sprytny, pracuj nad strukturami danych i algorytmami, ale nie mikrooptymalizuj ich ekspresji. Po prostu wróci, aby cię ugryźć, jeśli nie na bieżącym kompilatorze / architekturze, to na następnej.

W szczególności za pomocą arytmetyki wskaźników zamiast tablic i indeksy to trucizna dla kompilatora, który jest w pełni świadomy wyrównań, miejsc przechowywania, kwestii aliasingu i innych rzeczy, a także dla wykonywania optymalizacji, takich jak redukcja wytrzymałości w sposób najlepiej dostosowany do architektury maszyny.

Wektoryzacja może być tutaj użyta, jak to często ma miejsce w implementacjach memchr. Używasz następującego algorytmu:

1. Utwórz maskę powtarzającego się zapytania o długości równej liczbie bitów systemu operacyjnego (64-bit, 32-bit itp.). W systemie 64-bitowym powtórzyłbyś zapytanie 32-bitowe dwa razy.

2. Przetwarzaj listę jako listę wielu kawałków danych naraz, po prostu odlewając listę do listy większego typu danych i wyciągając wartości. Dla każdego kawałka, XOR to z maską, a następnie XOR z 0b0111...1, następnie dodaj 1, a następnie & z maską 0b1000...00: 00: 00 Jeśli wynik wynosi 0, to na pewno nie ma dopasowania. W przeciwnym razie, może (zwykle z bardzo dużym prawdopodobieństwem) być dopasowanie, więc przeszukać kawałek normalnie.

Przykładowa implementacja: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

Jeśli możesz pomieścić domenę swoich wartości za pomocą ilości pamięci dostępnej dla Twojej aplikacji, to najszybszym rozwiązaniem będzie reprezentowanie tablicy jako tablicy bitów:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

EDIT

Zamiast odrzucać tę odpowiedź, rozważ ją jako optymalny punkt wyjścia, dla którego możesz ewoluować za pomocą funkcji skrótu, aby osiągnąć lepszą równowagę między szybkością a wydajnością.

Przepraszam, jeśli moja odpowiedź już została udzielona - po prostu jestem leniwym czytelnikiem. W takim razie zapraszam do downvote))

1) można w ogóle usunąć licznik " i " - wystarczy porównać wskaźniki, czyli

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

Wszystko to nie da jednak znaczącej poprawy, taka optymalizacja prawdopodobnie mogłaby zostać osiągnięta przez sam kompilator.

2) Jak już wspomniano w innych odpowiedziach, prawie wszystkie nowoczesne procesory są oparte na RISC, na przykład ARM. Nawet nowoczesne procesory Intel X86 wykorzystują rdzenie RISC wewnątrz, z tego co wiem (kompilowanie z X86 w locie). Główną optymalizacją dla RISC jest optymalizacja rurociągów (a także dla Intela i innych procesorów), minimalizując skoki kodu. Jednym z rodzajów takiej optymalizacji (prawdopodobnie głównym) jest "cykl rollback". To jest niesamowicie głupie i wydajne, nawet kompilator Intela potrafi to zrobić AFAIK. Wygląda tak:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

W ten sposób optymalizacja polega na tym, że rurociąg nie jest uszkodzony w najgorszym przypadku( jeśli w tablicy nie ma compareVal), więc jest tak szybki jak możliwe (oczywiście nie licząc optymalizacji algorytmów, takich jak tabele hash, posortowane tablice itd., o których mowa w innych odpowiedziach, które mogą dać lepsze wyniki w zależności od wielkości tablicy. Cykle Rollback podejście może być stosowane tam, jak również przy okazji. Piszę tutaj o tym, że chyba nie widziałem w innych)

Druga część tej optymalizacji polega na tym, że pozycja tablicy jest pobierana przez adres bezpośredni( obliczony na etapie kompilacji, upewnij się, że używasz tablicy statycznej) i nie musisz dodatkowo dodaj op aby obliczyć wskaźnik z adresu bazowego tablicy. Ta optymalizacja może nie mieć znaczącego wpływu, ponieważ architektura ARM AFAIK ma specjalne funkcje przyspieszające adresowanie tablic. Ale w każdym razie zawsze lepiej jest wiedzieć, że zrobiłeś wszystko, co najlepsze tylko w kodzie C bezpośrednio, prawda?

Cofanie cyklu może wyglądać niezręcznie z powodu marnowania pamięci ROM( tak, dobrze zrobiłeś umieszczając go w szybkiej części pamięci RAM, jeśli Twoja płyta obsługuje tę funkcję), ale w rzeczywistości jest to uczciwa zapłata za szybkość, ponieważ opiera się na RISC concept. Jest to tylko ogólny punkt optymalizacji obliczeń - poświęcasz miejsce ze względu na szybkość i odwrotnie, w zależności od twoich wymagań.

Jeśli uważasz, że rollback dla tablicy 1024 elementów jest zbyt dużym poświęceniem dla Twojego przypadku, możesz rozważyć "częściowe rollback", na przykład dzieląc tablicę na 2 części po 512 elementów każda, lub 4x256, i tak dalej.

3) nowoczesne CPU często obsługują SIMD ops, np. ARM NEON instruction set - pozwala na wykonanie te same operacje równolegle. Szczerze mówiąc nie pamiętam, czy nadaje się do porównań, ale uważam, że może być, powinieneś to sprawdzić. Google pokazuje, że mogą być również pewne sztuczki, aby uzyskać maksymalną prędkość, zobacz https://stackoverflow.com/a/5734019/1028256

Jestem wielkim fanem haszowania. Problemem jest oczywiście znalezienie wydajnego algorytmu, który jest zarówno szybki, jak i zużywa minimalną ilość pamięci (szczególnie na wbudowanym procesorze).

Jeśli znasz wcześniej wartości, które mogą wystąpić, możesz utworzyć program, który działa za pomocą wielu algorytmów, aby znaleźć najlepszy-a raczej najlepsze parametry dla Twoich danych.

Stworzyłem taki program, o którym można przeczytać w ten post i osiągnąłem bardzo szybko wyniki. 16000 wpisów przekłada się z grubsza na 2^14 lub średnio 14 porównań, aby znaleźć wartość za pomocą wyszukiwania binarnego. Wyraźnie dążyłem do bardzo szybkich wyszukiwań-średnio znajdując wartość w wyszukiwaniach

Moje średnie wyszukiwanie wymagało około 60 cykli (na laptopie z intel i5) z algorytmem generycznym (z wykorzystaniem jednego podziału przez zmienną) i 40-45 cykli z wyspecjalizowanym (prawdopodobnie z wykorzystaniem mnożenia). Powinno to przełożyć się na czasy przeszukiwania sub-mikrosekundy na MCU, oczywiście w zależności od częstotliwości zegara, na którym jest wykonywany.

Może być jeszcze bardziej poprawiona w rzeczywistości, jeśli tablica wpisów śledzi, ile razy wpis był odwiedzany. Jeżeli wpis tablica jest sortowana od większości do najmniej dostępnych przed obliczeniem indeals, a następnie znajdzie najczęściej występujące wartości za pomocą jednego porównania.

To bardziej jak dodatek niż odpowiedź.

Miałem podobny w przeszłości, ale moja tablica była stała przez znaczną liczbę wyszukiwań.

W połowie z nich szukana wartość nie była obecna w tablicy. Potem zdałem sobie sprawę, że mogę zastosować "filtr" przed wykonaniem jakiegokolwiek wyszukiwania.

Ten "filtr" jest tylko prostą liczbą całkowitą, obliczoną raz i używaną przy każdym wyszukiwaniu.

Jest w Javie, ale to dość proste:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

Więc, przed wykonaniem wyszukiwania binarnego sprawdzam binaryfilter:

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

Możesz użyć 'lepszego' algorytmu skrótu, ale może to być bardzo szybkie, szczególnie dla dużych liczb. Może to zaoszczędzić jeszcze więcej cykli.