Domanda Come accoppiare i calzini da una pila in modo efficiente?


Ieri stavo abbinando i calzini alla lavanderia pulita e ho capito come stavo facendo non è molto efficiente. Stavo facendo una ricerca ingenua - scegliendo un calzino e "iterando" la pila per trovarne la coppia. Ciò richiede iterare su n / 2 * n / 4 = n2/ 8 calze in media.

Come informatico pensavo a cosa potevo fare? L'ordinamento (in base alla taglia / colore / ...), ovviamente, mi è venuto in mente per ottenere una soluzione O (NlogN).

L'hashing o altre soluzioni non sul posto non sono un'opzione, perché non sono in grado di duplicare i miei calzini (anche se potrebbe essere bello se potessi).

Quindi, la domanda è fondamentalmente:

Dato un mucchio di n paia di calze, contenenti 2n elementi (supponiamo che ogni calzino abbia esattamente una coppia corrispondente), qual è il modo migliore per associarli in modo efficiente con uno spazio extra logaritmico? (Credo di poter ricordare quella quantità di informazioni se necessario).

Apprezzerò una risposta che affronta i seguenti aspetti:

  • Un generale teorico soluzione per un enorme numero di calze.
  • Il numero effettivo di calzini non è così grande, non credo che mia moglie e io abbiamo più di 30 coppie. (Ed è abbastanza facile distinguere tra i miei calzini e quelli di lei, può essere usato anche questo?)
  • È equivalente al problema di distinzione degli elementi?

3501
2018-01-19 15:34


origine


risposte:


Sono state proposte soluzioni di ordinamento, ma l'ordinamento è un po 'troppo: Non abbiamo bisogno di ordine; abbiamo solo bisogno di gruppi di uguaglianza.

Così hashing sarebbe abbastanza (e più veloce).

  1. Per ogni colore di calzini, formare una pila. Fai scorrere tutte le calze nel tuo carrello di input e distribuirli sulle pile di colori.
  2. Iterate su ogni pila e distribuirlo con qualche altra metrica (ad esempio schema) nella seconda serie di pile
  3. Applicare ricorsivamente questo schema fino a quando non hai distribuito tutte le calze pile molto piccole che è possibile elaborare visivamente immediatamente

Questo tipo di partizionamento hash ricorsivo viene attualmente eseguito da server SQL quando ha bisogno di hash join o hash aggregati su enormi set di dati. Distribuisce il flusso di input di build in molte partizioni che sono indipendenti. Questo schema scala in modo lineare quantità arbitrarie di dati e più CPU.

Non è necessario il partizionamento ricorsivo se è possibile trovare una chiave di distribuzione (chiave hash) fornisce abbastanza secchi che ogni secchio è abbastanza piccolo per essere elaborato molto rapidamente. Sfortunatamente, non penso che i calzini abbiano una tale proprietà.

Se ogni calzino avesse un intero chiamato "PairID", si potrebbero facilmente distribuire in 10 secchi secondo PairID % 10 (l'ultima cifra).

Il miglior partizionamento del mondo reale che riesco a pensare è creare un rettangolo di pile: una dimensione è il colore, l'altra è il modello. Perché un rettangolo? Perché abbiamo bisogno di O (1) accesso casuale alle pile. (Un 3D cuboide funzionerebbe anche, ma non è molto pratico).


Aggiornare:

Che dire parallelismo? Possono più esseri umani abbinare i calzini più velocemente?

  1. La strategia di parallelizzazione più semplice è quella di far prelevare più lavoratori dal paniere di input e mettere i calzini sulle pile. Questo si riduce solo così tanto - immagina 100 persone che combattono più di 10 pile. I costi di sincronizzazione (manifestandosi come collisione delle mani e comunicazione umana) distruggere l'efficienza e accelerare (vedi il Legge universale sulla scalabilità!). È incline a questo deadlock? No, perché ogni lavoratore ha solo bisogno di accedere a una pila alla volta. Con un solo "lucchetto" non può esserci un deadlock. Livelocks potrebbe essere possibile a seconda di come gli umani coordinano l'accesso alle pile. Potrebbero semplicemente usare backoff casuale come le schede di rete farlo a livello fisico per determinare quale scheda può accedere esclusivamente al cavo di rete. Se funziona per NIC, dovrebbe funzionare anche per gli umani.
  2. Scala quasi indefinitamente se ogni lavoratore ha il proprio set di pile. I lavoratori possono quindi prelevare grossi pezzi di calze dal cesto di input (contesa molto raramente mentre lo fanno raramente) e non hanno bisogno di sincronizzarsi quando distribuiscono i calzini (perché hanno pile locali di thread). Alla fine, tutti i lavoratori hanno bisogno di unire le loro pile. Credo che possa essere fatto in O (log (conteggio dei lavoratori * pile per lavoratore)) se i lavoratori formano un albero di aggregazione.

Cosa ne pensi riguardo a problema di distinzione degli elementi? Come afferma l'articolo, il problema di distinzione degli elementi può essere risolto O(N). Questo è lo stesso per il problema dei calzini (anche O(N), se hai bisogno di una sola fase di distribuzione (ho proposto più passaggi solo perché gli umani sono cattivi ai calcoli - un passo è sufficiente se si distribuisce su md5(color, length, pattern, ...), cioè a hash perfetto di tutti gli attributi)).

Chiaramente, non si può andare più veloce di O(N), quindi abbiamo raggiunto il limite inferiore ottimale.

Sebbene le uscite non siano esattamente le stesse (in un caso, solo un booleano. Nell'altro caso, le coppie di calzini), le complessità asintotiche sono le stesse.


2176
2017-10-19 20:47



Poiché l'architettura del cervello umano è completamente diversa da una CPU moderna, questa domanda non ha alcun senso pratico.

Gli esseri umani possono conquistare gli algoritmi della CPU usando il fatto che "trovare una coppia corrispondente" può essere un'operazione per un set che non è troppo grande.

Il mio algoritmo:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

Almeno questo è quello che sto usando nella vita reale, e lo trovo molto efficiente. Il rovescio della medaglia è che richiede una superficie piatta, ma di solito è abbondante.


522
2018-05-27 19:13



Caso 1: Tutti i calzini sono identici (questo è quello che faccio nella vita reale, a proposito).

Scegli due di loro per fare una coppia. Tempo costante

Caso 2: Esiste un numero costante di combinazioni (proprietà, colore, dimensione, trama, ecc.).

Uso radix sort. Questo è solo il tempo lineare poiché il confronto non è richiesto.

Caso 3: Il numero di combinazioni non è noto in anticipo (caso generale).

Dobbiamo fare il confronto per verificare se due calze vengono in coppia. Scegli uno dei O(n log n) algoritmi di ordinamento basati sul confronto.

Tuttavia nella vita reale quando il numero di calze è relativamente piccolo (costante), questi algoritmi teoricamente ottimali non funzionerebbero bene. Potrebbe richiedere ancora più tempo della ricerca sequenziale, che teoricamente richiede il tempo quadratico.


231



Risposta non algoritmica, ma "efficiente" quando lo faccio:

  • passaggio 1) scartare tutte le calze esistenti

  • punto 2) vai a Walmart e comprali con pacchetti di 10 - n pacchetti di bianco e m pacchetti di nero. Non c'è bisogno di altri colori nella quotidianità vita.

Eppure, a volte, devo farlo di nuovo (calzini persi, calze danneggiate, ecc.), E odio scartare calze perfettamente buone troppo spesso (e avrei voluto che continuassero a vendere lo stesso riferimento ai calzini!), Quindi di recente ho preso un approccio diverso

Risposta algoritmica:

Considera che se disegni un solo calzino per il secondo paio di calze, come stai facendo, le probabilità di trovare il calzino corrispondente in una ricerca ingenua sono piuttosto basse.

  • Quindi prendine cinque di loro a caso, e memorizza la loro forma o la loro lunghezza.

Perché cinque? Di solito gli umani sono bravi a ricordare tra cinque e sette diversi elementi nella memoria di lavoro - un po 'come l'equivalente umano di a RPN stack - five è un valore predefinito sicuro.

  • Prendi uno dalla pila di 2n-5.

  • Ora cerca una corrispondenza (corrispondenza del modello visivo - gli umani sono bravi con una piccola pila) all'interno dei cinque che hai disegnato, se non ne trovi uno, quindi aggiungilo al tuo cinque.

  • Mantieni i calzini in ordine casuale e confronta i tuoi 5 + 1 calzini per una partita. Man mano che il tuo stack cresce, ridurrà le tue prestazioni ma aumenterà le tue probabilità. Più veloce.

Sentiti libero di scrivere la formula per calcolare quanti campioni devi disegnare per una quota del 50% di una partita. IIRC è una legge ipergeometrica.

Lo faccio tutte le mattine e raramente ho bisogno di più di tre estrazioni, ma ce l'ho n coppie simili (circa 10, danno o prendono quelle perse) di m calzini bianchi a forma di Ora puoi stimare la dimensione della mia pila di scorte :-)

BTW, Ho trovato che la somma dei costi di transazione di ordinare tutti i calzini ogni volta che avevo bisogno di una coppia era molto meno che farlo una volta e legare le calze. Un just-in-time funziona meglio perché non devi legare le calze, e c'è anche un rendimento marginale decrescente (ovvero, continui a cercare quei due o tre calzini che si trovano in un punto della lavanderia e di cui hai bisogno per finire di abbinare i tuoi calzini e perdi tempo su quello).


144



Quello che faccio è che prendo il primo calzino e lo metto giù (per esempio, sul bordo della tazza della lavanderia). Poi raccolgo un altro calzino e controllo per vedere se è lo stesso del primo calzino. Se lo è, li rimuovo entrambi. Se non lo è, lo metto vicino al primo calzino. Poi raccolgo il terzo calzino e lo confronto con i primi due (se sono ancora lì). Eccetera.

Questo approccio può essere facilmente implementato in un array, partendo dal presupposto che la rimozione di calze è un'opzione. In realtà, non è nemmeno necessario "rimuovere" i calzini. Se non hai bisogno di ordinare i calzini (vedi sotto), puoi semplicemente spostarli e finire con un array che ha tutte le calze disposte a coppie nell'array.

Supponendo che l'unica operazione per i calzini sia quella di confrontare per l'uguaglianza, questo algoritmo è fondamentalmente ancora un n2 algoritmo, anche se non conosco il caso medio (non ho mai imparato a calcolarlo).

L'ordinamento migliora naturalmente l'efficienza, soprattutto nella vita reale, dove puoi facilmente "inserire" un calzino tra due altri calzini. Nel calcolo lo stesso potrebbe essere ottenuto da un albero, ma quello è lo spazio extra. E, naturalmente, siamo tornati a NlogN (o un po 'di più, se ci sono diversi calzini che sono uguali per l'ordinamento dei criteri, ma non della stessa coppia).

Oltre a questo, non riesco a pensare a nulla, ma questo metodo sembra essere abbastanza efficiente nella vita reale. :)


92



Questa è la domanda sbagliata. La domanda giusta da porsi è, perché sto passando il tempo a classificare i calzini? Quanto costa su base annuale, quando valuti il ​​tuo tempo libero per unità monetarie X di tua scelta?

E il più delle volte, questo non è solo qualunque tempo libero, lo è mattina tempo libero, che si potrebbe spendere a letto, o sorseggiando il caffè, o lasciando un po 'presto e non essere presi nel traffico.

Spesso è bene fare un passo indietro e pensare ad un modo per aggirare il problema.

E c'è un modo!

Trova un calzino che ti piace. Tenere conto di tutte le caratteristiche rilevanti: colore in diverse condizioni di illuminazione, qualità generale e durata, comfort in diverse condizioni climatiche e assorbimento degli odori. Altrettanto importante è che non debbano perdere elasticità nello stoccaggio, quindi i tessuti naturali sono buoni e dovrebbero essere disponibili in un involucro di plastica.

È meglio se non c'è differenza tra i calzini del piede sinistro e quello del piede destro, ma non è fondamentale. Se le calze sono simmetriche sinistra-destra, trovare una coppia è un'operazione O (1), e l'ordinamento delle calze è un'operazione approssimativa di O (M), dove M è il numero di posti nella tua casa, che hai disseminato di calzini, idealmente alcuni piccolo numero costante.

Se hai scelto una coppia elegante con una calza sinistra e una destra diversa, facendo una sorta di benna completa per i secchi del piede sinistro e destro prendi O (N + M), dove N è il numero di calze e M è uguale a quello sopra. Qualcun altro può dare la formula per le iterazioni medie di trovare la prima coppia, ma il caso peggiore per trovare una coppia con la ricerca cieca è N / 2 + 1, che diventa astronomicamente improbabile nel caso di N. ragionevole Questo può essere accelerato usando l'immagine avanzata algoritmi di riconoscimento ed euristica, durante la scansione della pila di calzini non assortiti con Mk1 Eyeball.

Quindi, un algoritmo per ottenere l'efficienza di accoppiamento del calzino O (1) (assumendo un calzino simmetrico) è:

  1. Hai bisogno di stimare quante paia di calzini ti serviranno per il resto della tua vita, o forse fino a quando non ti ritirerai e passerai a climi più caldi senza bisogno di indossare di nuovo le calze. Se sei giovane, puoi anche stimare quanto tempo ci vorrà prima che tutti noi abbiamo i robot di smistamento delle calze nelle nostre case, e l'intero problema diventa irrilevante.

  2. Hai bisogno di scoprire come puoi ordinare il tuo calzino selezionato alla rinfusa, e quanto costa, e consegnano.

  3. Ordina le calze!

  4. Sbarazzati dei tuoi vecchi calzini.

Un passo alternativo 3 comporterebbe il confronto dei costi di acquisto della stessa quantità di calzini forse meno costosi poche paia alla volta nel corso degli anni e aggiungendo il costo della cernita dei calzini, ma credetemi: acquistare all'ingrosso è più economico! Inoltre, le calze in magazzino aumentano di valore al tasso di inflazione dei prezzi delle azioni, che è più di quanto si potrebbe ottenere su molti investimenti. Poi di nuovo c'è anche il costo di archiviazione, ma le calze non occupano molto spazio sul ripiano superiore di un armadio.

Problema risolto. Quindi, prendi nuovi calzini, getta / doni i tuoi vecchi e vivi felici e contenti dopo aver saputo che stai risparmiando denaro e tempo ogni giorno per il resto della tua vita.


50



Il limite teorico è O (n) perché è necessario toccare ciascun calzino (a meno che alcuni siano già accoppiati in qualche modo).

Puoi raggiungere O (n) con radix sort. Hai solo bisogno di scegliere alcuni attributi per i secchi.

  1. Per prima cosa puoi scegliere (il suo, il mio) - dividerli in 2 pile,
  2. quindi usa i colori (può avere qualsiasi ordine per i colori, ad esempio in ordine alfabetico per nome colore) - dividerli in pile per colore (ricorda di mantenere l'ordine iniziale dal punto 1 per tutti i calzini nella stessa pila),
  3. poi la lunghezza del calzino,
  4. poi trama, ....

Se puoi scegliere un numero limitato di attributi, ma abbastanza attributi che possono identificare in modo univoco ogni coppia, dovresti fare in O (k * n), che è O (n) se possiamo considerare che k è limitato.


47



Come soluzione pratica:

  1. Crea rapidamente pile di calzini facilmente distinguibili. (Dire per colore)
  2. Quicksort ogni pila e utilizzare la lunghezza del calzino per il confronto. Come umano, puoi prendere una decisione abbastanza veloce da utilizzare per partizione che eviti il ​​caso peggiore. (Puoi vedere più calze in parallelo, usalo a tuo vantaggio!)
  3. Smettete di smistare i mucchi quando raggiungono una soglia in cui vi sentite a vostro agio per trovare istantaneamente coppie di spiccioli e calzini inaccoppiati

Se hai 1000 calze, con 8 colori e una distribuzione media, puoi creare 4 pile di 125 calze in c * n. Con una soglia di 5 calzini puoi ordinare ogni pila in 6 serie. (Conteggio di 2 secondi per lanciare un calzino sulla pila giusta ci vorranno poco meno di 4 ore.)

Se hai solo 60 calze, 3 colori e 2 tipi di calze (tua / tua moglie) puoi ordinare ogni pila di 10 calzini in 1 serie (Ancora soglia = 5). (Conteggio 2 secondi ci vorranno 2 minuti).

L'ordinamento iniziale del bucket velocizzerà il tuo processo, perché divide i tuoi n calzini in k bucket in c*n tempo così che dovrai solo fare c*n*log(k) lavoro. (Non tenendo conto della soglia). Quindi tutto in tutto ciò che fai n*c*(1 + log(k)) lavoro, dove c è il momento di lanciare un calzino su una pila.

Questo approccio sarà favorevole rispetto a qualsiasi c*x*n + O(1) metodo approssimativamente lungo log(k) < x - 1.


In informatica può essere utile: Abbiamo una collezione di n cose, un ordine su di loro (lunghezza) e anche una relazione di equivalenza (informazioni extra, ad esempio il colore delle calze). La relazione di equivalenza ci consente di creare una partizione della collezione originale, e in ogni classe di equivalenza il nostro ordine è ancora mantenuto. La mappatura di a cosa alla sua classe di equivalenza può essere fatto in O (1), quindi è necessario solo O (n) per assegnare ciascun elemento ad una classe. Ora abbiamo utilizzato le nostre informazioni extra e possiamo procedere in qualsiasi modo per ordinare ogni classe. Il vantaggio è che i set di dati sono già significativamente più piccoli.

Il metodo può anche essere annidato, se abbiamo più relazioni di equivalenza -> crea pile di colori, che all'interno di ogni partizione di pila sulla trama, piuttosto che ordinare in base alla lunghezza. Qualsiasi relazione di equivalenza che crei una partizione con più di 2 elementi che abbiano dimensioni pari, porterà un miglioramento della velocità rispetto all'ordinamento (ammesso che possiamo assegnare direttamente un calzino alla sua pila) e l'ordinamento può avvenire molto rapidamente su insiemi di dati più piccoli.


31