Esiste un buon algoritmo di ricerca per un singolo personaggio?

Resta inteso che il caso peggiore è O(N) , ci sono alcune micro-ottimizzazioni molto belle.

Il metodo naive esegue un confronto di caratteri e un confronto di fine testo per ciascun carattere.

L'utilizzo di un sentinel (ovvero una copia del carattere di destinazione alla fine del testo) riduce il numero di confronti a 1 per carattere.

A livello di bit twiddling c'è:

#define haszero(v)      ( ((v) - 0x01010101UL) & ~(v) & 0x80808080UL )
#define hasvalue(x, n)  ( haszero((x) ^ (~0UL / 255 * (n))) )

per sapere se qualsiasi byte in una parola ( x ) ha un valore specifico ( n ).

La sottoespressione v - 0x01010101UL , valuta un bit elevato impostato in un byte qualsiasi quando il byte corrispondente in v è zero o maggiore di 0x80 .

La sottoespressione ~v & 0x80808080UL valuta i bit alti impostati in byte dove il byte di v non ha il suo bit di bit elevato (quindi il byte era inferiore a 0x80 ).

Con ANDing queste due sottoespressioni ( haszero ) il risultato sono i bit alti impostati dove i byte in v erano zero, poiché i bit alti sono stati impostati a causa di un valore maggiore di 0x80 nel primo sotto -espressione mascherata dal secondo (27 aprile 1987 da Alan Mycroft).

Ora possiamo XOR il valore da testare ( x ) con una parola che è stata riempita con il valore byte in cui siamo interessati ( n ). Poiché XORing di un valore con se stesso restituisce un byte zero e diverso da zero, possiamo passare il risultato a haszero .

Questo è spesso usato in un'implementazione tipica strchr .

(Stephen M Bennet lo ha suggerito il 13 dicembre 2009. Ulteriori dettagli nei ben noti Bit Twiding Hacks ).

PS

this code is broken for any combination of 1111's next to a 0

L'hack passa il test della forza bruta (solo essere paziente):

#include <iostream>
#include <limits>

bool haszero(std::uint32_t v)
{
  return (v - std::uint32_t(0x01010101)) & ~v & std::uint32_t(0x80808080);
}

bool hasvalue(std::uint32_t x, unsigned char n)
{
  return haszero(x ^ (~std::uint32_t(0) / 255 * n));
}

bool hasvalue_slow(std::uint32_t x, unsigned char n)
{
  for (unsigned i(0); i < 32; i += 8)
    if (((x >> i) & 0xFF) == n)
      return true;

  return false;
}

int main()
{
  const std::uint64_t stop(std::numeric_limits<std::uint32_t>::max());

  for (unsigned c(0); c < 256; ++c)
  {
    std::cout << "Testing " << c << std::endl;

    for (std::uint64_t w(0); w != stop; ++w)
    {
      if (w && w % 100000000 == 0)
        std::cout << w * 100 / stop << "%\r" << std::flush;

      const bool h(hasvalue(w, c));
      const bool hs(hasvalue_slow(w, c));

      if (h != hs)
        std::cerr << "hasvalue(" << w << ',' << c << ") is " << h << '\n';
    }
  }

  return 0;
}

Lots of upvotes for an answer which makes the assumption one chararacter=one byte, which is nowadays not the standard any more

Grazie per l'osservazione.

La risposta non era altro che un saggio su codifiche multi-byte / larghezza variabile :-) (in tutta onestà non è la mia area di competenza e non sono sicuro che sia ciò che l'OP stava cercando).

In ogni caso mi sembra che le idee / trucchi di cui sopra possano essere adattate in qualche modo a MBE (specialmente codifiche auto-sincronizzanti ):

• come indicato in Il commento di Johan l'hack può 'facilmente' essere esteso per funzionare con doppi byte o altro (ovviamente non puoi allungarlo troppo);
• una funzione tipica che individua un carattere in una stringa di caratteri multibyte:
  • contiene chiamate a strchr / strstr (ad es. GNUlib coreutils mbschr )
  • si aspetta che siano ottimizzati.
• la tecnica sentinella può essere utilizzata con un po 'di lungimiranza.

Qualsiasi algoritmo di ricerca del testo che ricerca ogni occorrenza di un singolo carattere in un determinato testo deve leggere ogni carattere del testo almeno una volta, che dovrebbe essere ovvio. E poiché questo è sufficiente per una ricerca una tantum, non ci può essere un algoritmo migliore (quando si pensa in termini di ordine di esecuzione, che è chiamato "lineare" o O (N) per questo caso, dove N è il numero di caratteri per cercare attraverso.

Tuttavia, per le implementazioni reali, ci sono sicuramente molte micro-ottimizzazioni possibili, che non modificano l'ordine di esecuzione nel suo complesso, ma riducono il tempo di esecuzione effettivo. E se l'obiettivo non è quello di trovare tutte le occorrenze di un singolo personaggio, ma solo il primo, è possibile fermarsi alla prima occorrenza, ovviamente. Tuttavia, anche in quel caso, il caso peggiore è che il personaggio che stai cercando sia l'ultimo carattere nel testo, quindi l'ordine di esecuzione del caso peggiore per questo obiettivo è ancora O (N).

Se il tuo "pagliaio" viene cercato più di una volta, un approccio basato sull'istogramma sarà estremamente veloce. Una volta creato l'istogramma, è sufficiente una ricerca del puntatore per trovare la risposta.

Se hai solo bisogno di sapere se il modello cercato è presente, può essere utile un semplice contatore. Può essere esteso per includere la posizione (s) in cui ogni personaggio si trova nel pagliaio o la posizione della prima occorrenza.

string haystack = "agtuhvrth";
array<int, 256> histogram{0};
for(character: haystack)
     ++histogram[character];

if(histogram['a'])
    // a belongs to haystack

Se hai bisogno di cercare i caratteri in questa stessa stringa più di una volta, allora un possibile approccio è quello di dividere la stringa in parti più piccole, possibilmente ricorsivamente, e di usare i filtri di fioritura per ciascuna di queste parti.

Dato che un filtro di fioritura può dirti con certezza se un personaggio è non nella parte della stringa che è "rappresentata" dal filtro, puoi saltare alcune parti mentre cerchi i caratteri.

Come esempio: per la seguente stringa si può dividerlo in 4 parti (ciascuna di 11 caratteri) e riempire per ogni parte un filtro di fioritura (forse di 4 byte di grandi dimensioni) con i caratteri di quella parte:

The quick brown fox jumps over the lazy dog 
          |          |          |          |

Puoi velocizzare la ricerca, ad es. per il carattere a : Usando buone funzioni di hash per i filtri di fioritura, ti diranno che - con alta probabilità - non devi cercare né la prima né la seconda né la terza parte. Così ti risparmi dal controllare 33 caratteri e invece devi solo controllare 16 byte (per i 4 filtri di fioritura). Questo è ancora O(n) , solo con un fattore costante (frazionario) (e affinché questo sia efficace dovrai scegliere parti più grandi, per ridurre al minimo il sovraccarico del calcolo delle funzioni hash per il carattere di ricerca).

L'utilizzo di un approccio ricorsivo simile ad un albero dovrebbe avvicinarti a O(log n) :

The quick brown fox jumps over the lazy dog 
   |   |   |   |   |   |   |   |---|-X-|   |  (1 Byte)
       |       |       |       |---X---|----  (2 Byte)
               |               |-----X------  (3 Byte)
-------------------------------|-----X------  (4 Byte)
---------------------X---------------------|  (5 Byte)

In questa configurazione è necessario (ancora una volta, supponendo che siamo stati fortunati e non abbiamo ottenuto un falso positivo da uno dei filtri) per controllare

5 + 2*4 + 3 + 2*2 + 2*1 bytes

per arrivare alla parte finale (dove è necessario controllare 3 caratteri fino a trovare il a ).

Usando uno schema di suddivisione buono (meglio come sopra) dovresti ottenere risultati molto belli con quello. (Nota: i filtri Bloom nella radice dell'albero devono essere più grandi di quelli vicini alle foglie, come mostrato nell'esempio, per ottenere una probabilità bassa di falsi positivi)

Se la stringa verrà cercata più volte (tipico problema di "ricerca"), la soluzione può essere O (1). La soluzione è costruire un indice.

E.g:

Mappa, dove Chiave è il Carattere e Valore è un elenco di indici per quel carattere nella stringa.

Con questo, una singola ricerca di mappe può fornire la risposta.