Comment associer efficacement les chaussettes d'une pile ?

Question

Hier, j'associais les chaussettes du linge propre et je me suis rendu compte que la façon dont je le faisais n'était pas très efficace. Je faisais une recherche naïve - je choisissais une chaussette et "itérais" la pile afin de trouver sa paire. Cela nécessite d'itérer sur n/2 * n/4 = n 2 /8 chaussettes en moyenne.

En tant qu'informaticien, je me suis demandé ce que je pouvais faire... Le tri (selon la taille/couleur/...) m'est bien sûr venu à l'esprit pour obtenir une solution O(NlogN).

Le hachage ou d'autres solutions de type "not-in-place" ne sont pas une option, car je ne suis pas en mesure de dupliquer mes chaussettes (même si ce serait bien si je le pouvais).

Donc, la question est essentiellement :

Étant donné une pile de n paires de chaussettes, contenant 2n (en supposant que chaque chaussette a exactement une paire correspondante), quelle est la meilleure façon de les apparier efficacement avec un espace supplémentaire pouvant atteindre le logarithme ? (Je crois que je peux me souvenir de cette quantité d'informations si nécessaire).

J'apprécierai une réponse qui aborde les aspects suivants :

• Un général théorique solution pour un grand nombre de chaussettes.
• Le nombre réel de chaussettes n'est pas si important, je ne crois pas que mon conjoint et moi ayons plus de 30 paires. (Et il est assez facile de distinguer mes chaussettes des siennes ; cela peut-il être utilisé également) ?
• Est-il équivalent à la le problème de la distinction des éléments ?

Answer 1

Des solutions de tri ont été proposées, mais le triage est un peu trop poussé : Nous n'avons pas besoin d'ordre ; nous avons juste besoin de groupes d'égalité .

Alors hachage serait suffisant (et plus rapide).

1. Pour chaque couleur de chaussettes, former une pile . Itérer sur toutes les chaussettes de votre panier d'entrée. et les distribuer sur les piles de couleur .
2. Itérer sur chaque pile et le distribuer selon une autre métrique (par exemple, un motif) dans le deuxième ensemble de piles
3. Appliquer récursivement ce schéma jusqu'à ce que vous ayez distribué toutes les chaussettes sur de très petits tas que vous pouvez traiter visuellement immédiatement

Ce type de partitionnement récursif du hachage est en fait effectué par SQL Server lorsqu'il doit effectuer des jointures ou des agrégations par hachage sur d'énormes ensembles de données. Il distribue son flux d'entrée de construction dans de nombreuses partitions qui sont indépendantes. Ce schéma s'adapte linéairement à des quantités arbitraires de données et à plusieurs processeurs.

Vous n'avez pas besoin de partitionnement récursif si vous pouvez trouver une clé de distribution (clé de hachage) qui fournit suffisamment de seaux que chaque seau est assez petit pour être traité très rapidement. Malheureusement, je ne pense pas que les chaussettes aient une telle propriété.

Si chaque chaussette possédait un entier appelé "PairID", on pourrait facilement les répartir dans 10 godets en fonction des critères suivants PairID % 10 (le dernier chiffre).

Le meilleur partitionnement dans le monde réel auquel je peux penser est la création d'une rectangle de pieux : une dimension est la couleur, l'autre est le motif. Pourquoi un rectangle ? Parce que nous avons besoin d'un accès aléatoire O(1) aux piles. (UNE IMAGE 3D cuboïde fonctionnerait également, mais ce n'est pas très pratique).

---

Mise à jour :

Qu'en est-il parallélisme ? Plusieurs humains peuvent-ils assortir les chaussettes plus rapidement ?

1. La stratégie de parallélisation la plus simple consiste à demander à plusieurs travailleurs de prendre dans le panier d'entrée et de mettre les chaussettes sur les piles. Cette stratégie n'a qu'une portée limitée - imaginez 100 personnes se battant pour 10 piles. Les coûts de synchronisation (se manifestant par des collisions de mains et la communication humaine) détruire l'efficacité et la rapidité (voir le Loi universelle d'extensibilité !). Est-ce que cela risque de blocages ? Non, car chaque travailleur n'a besoin d'accéder qu'à une seule pile à la fois. Avec un seul "verrou", il ne peut y avoir d'impasse. Sas d'entrée pourrait être possible selon la façon dont les humains coordonnent l'accès aux piles. Ils pourraient simplement utiliser backoff aléatoire comme les cartes réseau le font au niveau physique pour déterminer quelle carte peut accéder exclusivement au fil du réseau. Si cela fonctionne pour NICs cela devrait fonctionner pour les humains aussi.
2. Il s'adapte presque indéfiniment si chaque travailleur a son propre ensemble de piles . Les travailleurs peuvent alors prendre de gros morceaux de chaussettes dans le panier d'entrée (très peu de contention car ils le font rarement) et ils n'ont pas besoin de se synchroniser lors de la distribution des chaussettes (parce qu'ils ont des piles locales). À la fin, tous les travailleurs doivent unir leurs ensembles de piles. Je pense que cela peut être fait en O(log (nombre de travailleurs * piles par travailleur)) si les travailleurs forment une arbre de regroupement .

Qu'en est-il de la le problème de la distinction des éléments ? Comme l'indique l'article, le problème de la distinction des éléments peut être résolu en O(N) . Il en va de même pour le problème des chaussettes (également O(N) si vous n'avez besoin que d'une seule étape de distribution (je propose plusieurs étapes uniquement parce que les humains sont mauvais en calcul - une étape est suffisante si vous distribuez sur md5(color, length, pattern, ...) c'est-à-dire une hachis parfait de tous les attributs)).

Clairement, on ne peut pas aller plus vite que O(N) donc nous avons atteint le limite inférieure optimale .

Bien que les résultats ne soient pas exactement les mêmes (dans un cas, juste un booléen, dans l'autre cas, les paires de chaussettes), les complexités asymptotiques sont les mêmes.

Answer 2

L'architecture du cerveau humain étant complètement différente de celle d'un processeur moderne, cette question n'a aucun sens pratique.

Les humains peuvent l'emporter sur les algorithmes des CPU en utilisant le fait que "trouver une paire correspondante" peut être une opération pour un ensemble qui n'est pas trop grand.

Mon algorithme :

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);
}

C'est du moins ce que j'utilise dans la vie réelle, et je le trouve très efficace. L'inconvénient est qu'il faut une surface plane, mais elle est généralement abondante.

Answer 3

Cas 1 : Toutes les chaussettes sont identiques (c'est ce que je fais dans la vraie vie d'ailleurs).

Choisissez deux d'entre eux pour former une paire. Temps constant.

Cas 2 : Il existe un nombre constant de combinaisons (propriété, couleur, taille, texture, etc.).

Utilice tri radix . Il s'agit uniquement d'un temps linéaire puisque la comparaison n'est pas nécessaire.

Cas 3 : Le nombre de combinaisons n'est pas connu à l'avance (cas général).

Nous devons faire une comparaison pour vérifier si deux chaussettes vont par paire. Choisissez l'une des O(n log n) les algorithmes de tri basés sur la comparaison.

Cependant, dans la vie réelle, lorsque le nombre de chaussettes est relativement faible (constant), ces algorithmes théoriquement optimaux ne fonctionneraient pas bien. Cela pourrait même prendre plus de temps que la recherche séquentielle, qui nécessite théoriquement un temps quadratique.

Answer 4

Réponse non algorithmique, mais "efficace" quand je le fais :

• étape 1) jetez toutes vos chaussettes existantes

• étape 2) aller à Walmart et les acheter par paquets de 10 - n paquet de blanc et m paquets de noir. Pas besoin d'autres couleurs dans la vie de tous les jours quotidienne.

Pourtant, de temps en temps, je dois recommencer (chaussettes perdues, chaussettes abîmées, etc.), et je déteste jeter trop souvent des chaussettes parfaitement bonnes (et j'aurais aimé qu'ils continuent à vendre les mêmes chaussettes de référence !), alors j'ai récemment adopté une approche différente.

Réponse algorithmique :

Considérez que si vous ne tirez qu'une seule chaussette pour la deuxième pile de chaussettes, comme vous le faites, vos chances de trouver la chaussette correspondante lors d'une recherche naïve sont assez faibles.

• Prenez-en donc cinq au hasard, et mémorisez leur forme ou leur longueur.

Pourquoi cinq ? En général, les êtres humains sont capables de se souvenir de cinq à sept éléments différents dans leur mémoire de travail - un peu comme l'équivalent humain d'une carte de crédit. RPN stack - cinq est une valeur sûre par défaut.

• Prenez-en un dans la pile de 2n-5.

• Maintenant, cherchez une correspondance (correspondance visuelle - les humains sont doués pour cela avec une petite pile) à l'intérieur des cinq que vous avez dessinés, si vous n'en trouvez pas, ajoutez-la à vos cinq.

• Continuez à prendre des chaussettes au hasard dans la pile et comparez-les à vos 5+1 chaussettes pour trouver une correspondance. Au fur et à mesure que votre pile grandira, cela réduira vos performances mais augmentera vos chances. Beaucoup plus rapide.

N'hésitez pas à écrire la formule permettant de calculer le nombre d'échantillons à prélever pour avoir 50 % de chances d'obtenir une correspondance. Il s'agit d'une loi hypergéométrique.

Je fais cela tous les matins et j'ai rarement besoin de plus de trois tirages - mais j'ai n paires similaires (environ 10, en tenant compte de celles qui ont été perdues) de m chaussettes blanches en forme. Vous pouvez maintenant estimer la taille de ma pile d'actions :-)

BTW J'ai constaté que la somme des coûts de transaction liés au tri de toutes les chaussettes chaque fois que j'avais besoin d'une paire était bien inférieure à la somme des coûts de transaction liés au tri unique et à la reliure des chaussettes. Un juste-à-temps fonctionne mieux parce qu'alors vous n'avez pas à lier les chaussettes, et il y a aussi un rendement marginal décroissant (c'est-à-dire que vous continuez à chercher ces deux ou trois chaussettes qui se trouvent quelque part dans la buanderie et dont vous avez besoin pour finir d'assortir vos chaussettes et vous perdez du temps là-dessus).

Answer 5

Ce que je fais, c'est que je prends la première chaussette et la pose (disons sur le bord de la cuvette à linge). Puis je prends une autre chaussette et je vérifie si elle est identique à la première. Si c'est le cas, je les enlève toutes les deux. Si elle ne l'est pas, je la pose à côté de la première chaussette. Puis je prends la troisième chaussette et je la compare aux deux premières (si elles sont toujours là). Etc.

Cette approche peut être assez facilement mise en œuvre dans un tableau, en supposant que la "suppression" des chaussettes est une option. En fait, vous n'avez même pas besoin de "retirer" les chaussettes. Si vous n'avez pas besoin de trier les chaussettes (voir ci-dessous), vous pouvez simplement les déplacer et vous retrouver avec un tableau dans lequel toutes les chaussettes sont disposées par paires.

En supposant que la seule opération pour les chaussettes est de comparer pour l'égalité, cet algorithme est fondamentalement toujours un n 2 algorithme, mais je ne connais pas le cas moyen (je n'ai jamais appris à le calculer).

Le tri améliore bien sûr l'efficacité, surtout dans la vie réelle où l'on peut facilement "insérer" une chaussette entre deux autres chaussettes. En informatique, la même chose pourrait être obtenue par un arbre, mais c'est de l'espace supplémentaire. Et, bien sûr, on revient à NlogN (ou un peu plus, s'il y a plusieurs chaussettes qui sont les mêmes selon les critères de tri, mais pas de la même paire).

En dehors de cela, je ne vois rien d'autre, mais cette méthode semble être assez efficace dans la vie réelle. :)