Question Comment jumeler efficacement les chaussettes d'une pile?


Hier, je faisais la paire avec les chaussettes de la lessive propre et j'ai compris que la façon dont je le faisais n'était pas très efficace. Je faisais une recherche naïve - choisir une chaussette et "itérer" la pile afin de trouver sa paire. Cela nécessite d'itérer sur n / 2 * n / 4 = n2/ 8 chaussettes en moyenne.

En tant qu'informaticien, je pensais à ce que je pouvais faire? Le tri (en fonction de la taille / couleur / ...) est bien entendu venu à l'esprit pour obtenir une solution O (NlogN).

Hashing ou d'autres solutions non-sur place ne sont pas une option, parce que je ne suis pas capable de dupliquer mes chaussettes (même si cela pourrait être bien si je le pouvais).

Donc, la question est essentiellement:

Étant donné un tas de n paires de chaussettes, contenant 2n éléments (supposons que chaque chaussette a exactement une paire correspondante), quelle est la meilleure façon de les associer efficacement avec un espace supplémentaire logarithmique? (Je crois que je peux me rappeler cette quantité d'information 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 grand, je ne crois pas mon conjoint et moi avons plus de 30 paires. (Et il est assez facile de distinguer entre mes chaussettes et les siennes, cela peut-il être aussi bien utilisé?)
  • Est-ce l'équivalent de problème de distinction d'élément?

3501
2018-01-19 15:34


origine


Réponses:


Des solutions de tri ont été proposées, mais le tri est un peu trop: 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 distribuez-les sur les piles de couleurs.
  2. Itérer sur chaque pile et le distribuer par une autre métrique (par exemple, motif) dans le second ensemble de piles
  3. Appliquer récursivement ce schéma jusqu'à ce que vous ayez distribué toutes les chaussettes très petites piles que vous pouvez traiter visuellement immédiatement

Ce genre de partitionnement de hachage récursif est en train d'être fait par serveur SQL quand il a besoin de se joindre à un hash ou d'agréger un hachage sur d'énormes ensembles de données. Il distribue son flux d'entrée de construction dans de nombreuses partitions 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) fournit assez de seaux que chaque seau est suffisamment petit pour être traité très rapidement. Malheureusement, je ne pense pas que les chaussettes aient une telle propriété.

Si chaque chaussette avait un entier appelé "PairID", on pourrait facilement les distribuer en 10 seaux selon PairID % 10 (le dernier chiffre).

Le meilleur partitionnement réel que je puisse penser est de créer un rectangle de piles: une dimension est la couleur, l'autre est le motif. Pourquoi un rectangle? Parce que nous avons besoin de O (1) accès aléatoire aux piles. (Une 3D cuboïde ça marcherait aussi, mais ce n'est pas très pratique.)


Mettre à jour:

Qu'en est-il de parallélisme? Plusieurs humains peuvent-ils correspondre aux chaussettes plus rapidement?

  1. La stratégie de parallélisation la plus simple consiste à prendre plusieurs travailleurs du panier d'entrée et à mettre les chaussettes sur les piles. Cela ne fait que s'améliorer - imaginez 100 personnes se disputant plus de 10 piles. Les coûts de synchronisation (Se manifestant comme des collisions de la main et de la communication humaine) détruire l'efficacité et accélérer (voir le Loi universelle sur l'évolutivité!). Est-ce sujet à deadlocks? Non, car chaque travailleur n'a besoin que d'accéder à une pile à la fois. Avec un seul "verrou", il ne peut y avoir d'impasse. Livelocks pourrait être possible en fonction de la façon dont les humains coordonnent l'accès aux piles. Ils pourraient juste utiliser backoff aléatoire comme les cartes réseau le font au niveau physique pour déterminer quelle carte peut accéder exclusivement au réseau. Si cela fonctionne pour NIC, ça devrait marcher aussi pour les humains.
  2. Il évolue presque indéfiniment si chaque travailleur a son propre ensemble de piles. Les travailleurs peuvent alors prendre de gros morceaux de chaussettes à partir du panier d'entrée (très peu de contention comme 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 piles. Je crois que cela peut être fait en O (log (nombre de travailleurs * piles par travailleur)) si les travailleurs forment un arbre d'agrégation.

Que dire de la problème de distinction d'élément? Comme le dit l'article, le problème de la distinction des éléments peut être résolu O(N). C'est la même chose pour le problème des chaussettes (aussi O(N), si vous avez besoin d'une seule étape de distribution (j'ai proposé plusieurs étapes uniquement parce que les humains sont mauvais lors des calculs - une étape suffit si vous distribuez sur md5(color, length, pattern, ...), c'est-à-dire un hachage parfait de tous les attributs)).

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

Bien que les sorties 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.


2176
2017-10-19 20:47



Comme l'architecture du cerveau humain est complètement différente d'une CPU moderne, cette question n'a aucun sens pratique.

Les humains peuvent gagner des algorithmes de 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);
}

Au moins c'est ce que j'utilise dans la vraie vie, et je le trouve très efficace. L'inconvénient est qu'il nécessite une surface plane, mais il est généralement abondant.


522
2018-05-27 19:13



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

Choisissez-en deux pour faire une paire. Temps constant.

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

Utilisation type de base. Ceci est seulement le 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 viennent en paire. Choisissez l'un des O(n log n) algorithmes de tri basés sur la comparaison.

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


231



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 blancs et m paquets de noir. Pas besoin d'autres couleurs dans tous les jours la vie.

Pourtant, parfois, je dois le refaire (chaussettes perdues, chaussettes abîmées, etc.), et je déteste me débarrasser trop souvent de bonnes chaussettes (et j'aurais aimé qu'elles continuent à vendre la même référence!), Alors j'ai récemment pris une approche différente.

Réponse algorithmique:

Considérons que si vous ne dessinez qu'une chaussette pour la deuxième pile de chaussettes, comme vous le faites, vos chances de trouver la chaussette correspondante dans une recherche naïve est assez faible.

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

Pourquoi cinq? Habituellement, les humains sont bons, ils se souviennent entre cinq et sept éléments différents dans la mémoire de travail - un peu comme l'équivalent humain d'un RPN pile - cinq est un défaut par défaut.

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

  • Maintenant, cherchez un match (correspondance visuelle - les humains sont bons avec une petite pile) dans les cinq que vous avez dessinés, si vous n'en trouvez pas, ajoutez-les à vos cinq.

  • Gardez au hasard les chaussettes de la pile et comparez-les à vos chaussettes 5 + 1 pour un match. Au fur et à mesure de la croissance de votre pile, cela réduira vos performances mais augmentera vos chances. Plus vite.

N'hésitez pas à noter la formule pour calculer le nombre d'échantillons que vous devez prélever pour obtenir une cote de 50%. IIRC c'est 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, donner ou prendre les perdus) de m chaussettes blanches en forme. Maintenant, vous pouvez estimer la taille de ma pile de stocks :-)

BTW, J'ai trouvé que la somme des coûts de transaction de tri de toutes les chaussettes chaque fois que j'avais besoin d'une paire était beaucoup moins que de le faire une fois et de lier les chaussettes. Un juste-à-temps fonctionne mieux parce que vous n'avez pas besoin de 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 quand vous êtes dans la buanderie pour finir de faire correspondre vos chaussettes et vous perdez du temps là-dessus).


144



Ce que je fais, c'est que je prends la première chaussette et la pose (par exemple, sur le bord de la cuve). Ensuite, je prends une autre chaussette et vérifie pour voir si c'est la même que la première chaussette. Si c'est le cas, je les enlève tous les deux. Si ce n'est pas le cas, je l'ai posé à côté de la première chaussette. Ensuite, je prends la troisième chaussette et compare cela aux deux premiers (s'ils sont toujours là). Etc.

Cette approche peut être assez facilement mise en œuvre dans un tableau, en supposant que "supprimer" les 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 finir avec un tableau qui a toutes les paires disposées par paires dans le tableau.

En supposant que la seule opération pour les chaussettes est de comparer pour l'égalité, cet algorithme est fondamentalement toujours un n2 algorithme, bien que je ne sais pas sur le cas moyen (jamais appris à calculer cela).

Le tri, bien sûr améliore l'efficacité, en particulier dans la vie réelle où vous pouvez facilement "insérer" une chaussette entre deux autres chaussettes. En calculant le même pourrait être réalisé par un arbre, mais c'est un espace supplémentaire. Et, bien sûr, nous sommes de retour à NlogN (ou un peu plus, s'il y a plusieurs chaussettes qui sont identiques par des critères de tri, mais pas de la même paire).

À part ça, je ne peux penser à rien, mais cette méthode semble être assez efficace dans la vraie vie. :)


92



C'est poser la mauvaise question. La bonne question à poser est, pourquoi je passe du temps à trier les chaussettes? Combien cela coûte-t-il sur une base annuelle, quand vous appréciez votre temps libre pour X unités monétaires de votre choix?

Et plus souvent qu'autrement, ce n'est pas seulement tout temps libre, c'est Matin temps libre, que vous pourriez passer au lit, ou en sirotant votre café, ou en laissant un peu tôt et ne pas être pris dans la circulation.

Il est souvent bon de prendre du recul et de trouver une solution au problème.

Et il y a un moyen!

Trouvez une chaussette que vous aimez. Tenir compte de toutes les caractéristiques pertinentes: la couleur dans différentes conditions d'éclairage, la qualité et la durabilité globales, le confort dans différentes conditions climatiques et l'absorption des odeurs. Il est également important qu'ils ne perdent pas leur élasticité lors du stockage, de sorte que les tissus naturels soient bons et qu'ils soient disponibles dans un emballage en plastique.

C'est mieux s'il n'y a pas de différence entre les chaussettes de pied gauche et droite, mais ce n'est pas critique. Si les chaussettes sont symétriques gauche-droite, trouver une paire est une opération O (1), et le tri des chaussettes est approximatif O (M), où M est le nombre de places dans votre maison, que vous avez jonché de chaussettes, idéalement petit nombre constant.

Si vous avez choisi une paire fantaisie avec différentes chaussettes gauche et droite, faire un tri complet du godet pour les godets de pied gauche et droit prend O (N + M), où N est le nombre de chaussettes et M est le même que ci-dessus. Quelqu'un d'autre peut donner la formule pour les itérations moyennes de trouver la première paire, mais le pire des cas pour trouver une paire avec recherche aveugle est N / 2 + 1, ce qui devient astronomique pour N raisonnable. Cela peut être accéléré en utilisant l'image avancée algorithmes de reconnaissance et heuristiques, lors de l'analyse de la pile de chaussettes non triés avec Mk1 globe oculaire.

Ainsi, un algorithme pour atteindre l'efficacité de l'appariement des chaussettes O (1) (en supposant une chaussette symétrique) est:

  1. Vous devez estimer le nombre de paires de chaussettes dont vous aurez besoin pour le reste de votre vie, ou peut-être jusqu'à ce que vous preniez votre retraite et déménagiez dans des climats plus chauds sans avoir besoin de porter des chaussettes encore une fois. Si vous êtes jeune, vous pouvez également estimer combien de temps cela prendra avant que nous ayons tous des robots de tri dans nos maisons, et tout le problème devient hors de propos.

  2. Vous devez savoir comment vous pouvez commander votre chaussette sélectionnée en vrac, combien elle coûte et livrez-vous.

  3. Commandez les chaussettes!

  4. Débarrassez-vous de vos vieilles chaussettes.

Une autre étape 3 consisterait à comparer les coûts d'achat de la même quantité de chaussettes moins chères, quelques paires à la fois au fil des ans et le coût de tri des chaussettes, mais croyez-moi: l'achat en vrac coûte moins cher! En outre, les chaussettes en stock augmentent en valeur au taux de l'inflation des prix des actions, ce qui est plus que ce que vous obtiendriez sur de nombreux investissements. Là encore, il y a aussi le coût de stockage, mais les chaussettes ne prennent vraiment pas beaucoup d'espace sur l'étagère supérieure d'un placard.

Problème résolu. Alors, procurez-vous de nouvelles chaussettes, jetez / donnez vos anciens, et vivez heureux après avoir su que vous économisez de l'argent et du temps chaque jour pour le reste de votre vie.


50



La limite théorique est O (n) car vous devez toucher chaque chaussette (à moins que certaines ne soient déjà jumelées).

Vous pouvez atteindre O (n) avec type de base. Vous avez juste besoin de choisir quelques attributs pour les seaux.

  1. D'abord vous pouvez choisir (le sien, le mien) - les diviser en 2 piles,
  2. utilisez ensuite des couleurs (pouvez avoir n'importe quel ordre pour les couleurs, par exemple alphabétiquement par nom de couleur) - les diviser en piles par couleur (n'oubliez pas de conserver l'ordre initial de l'étape 1 pour toutes les chaussettes de la même pile),
  3. puis la longueur de la chaussette,
  4. puis texture, ....

Si vous pouvez choisir un nombre limité d'attributs, mais assez d'attributs qui peuvent identifier chaque paire, vous devriez le faire dans O (k * n), qui est O (n) si nous pouvons considérer que k est limité.


47