Implementazione della programmazione di ricerca binaria

1

Ricerca binaria, come tutti sappiamo richiede che gli elementi siano ordinati. Ma dobbiamo anche occuparci di elementi non differenziati, nel peggiore dei casi. Se la dimensione dell'input è molto grande, è una buona idea ordinare gli elementi ogni volta? Non possiamo semplicemente controllare gli elementi che non sono ordinati o meno e procedere all'ordinamento e procedere all'ordinamento solo se non sono ordinati?

    
posta user1369975 24.05.2013 - 14:23
fonte

3 risposte

6

controllando se una lista è ordinata sconfigge lo scopo della ricerca binaria (usando meno confronti per un tempo di esecuzione O(log n) invece di un O(n) )

è meglio fare una ricerca lineare se non si è sicuri che l'elenco sia già ordinato

    
risposta data 24.05.2013 - 14:29
fonte
1

Ho dovuto affrontare qualcosa di simile molto tempo fa.

Mantenere un grande file ordinato e un piccolo file non ordinato. Quello piccolo contiene elementi che non sono ancora stati uniti. Cerca prima quello piccolo e, se fallisce, cerca quello grande. "Ogni tanto", come quando il piccolo file diventa una frazione della dimensione del file di grandi dimensioni, ordina il file piccolo e quindi lo unisci a quello grande.

    
risposta data 24.05.2013 - 17:33
fonte
0

Ero di fronte a questo problema proprio ieri. Ecco tre informazioni che posso offrire che potrebbero aiutare:

  1. Prova a mantenere una vista del database dei dati che devi interrogare che è sempre ordinata. Ad esempio, ho avuto un enorme (500k records), tabella di dati non ordinata che conteneva, tra le altre cose, una colonna per CompanyName . Nella mia applicazione, avevo bisogno di cercare questi record in base a un determinato nome di società, che è maturo per una ricerca binaria. Ho semplicemente creato una vista SQL ordinata che contiene solo CompanyName e id (che è la chiave primaria nella tabella originale ". Ora interrogando direttamente dall'applicazione e ottenendo il risultato in meno di 10 ms.
  2. Se non puoi garantire in anticipo che il tuo set di dati è ordinato, fai un buon uso di hashtables e guarda " Ordinamento rapido " algoritmo. Questo è un algoritmo O (log n) quindi se lo esegui prima e poi una ricerca binaria contro i tuoi dati è sicuramente più veloce di una ricerca lineare.
  3. Inoltre, prova a fare un buon uso del caching: se hai già ordinato un determinato set di dati, non c'è motivo di farlo di nuovo per la prossima query.

Buona fortuna!

    
risposta data 24.05.2013 - 17:52
fonte

Leggi altre domande sui tag