variable - repeat algorithm latex




Comment coupler efficacement les chaussettes d'un tas? (20)

Hier, je jumelais les chaussettes de la lessive propre et je me suis rendu compte que ce que je faisais n’est pas très efficace. Je faisais une recherche naïve - en choisissant une chaussette et en "itérant" la pile afin de trouver sa paire. Cela nécessite une itération sur n / 2 * n / 4 = n 2/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 sûr venu à l’esprit pour obtenir une solution O (NlogN).

Le hachage ou d'autres solutions non sur place ne sont pas une option, car je ne suis pas en mesure de dupliquer mes chaussettes (bien que cela puisse être agréable si je le pouvais).

Donc, la question est fondamentalement:

Avec une pile de n paires de chaussettes contenant 2n éléments (en supposant que chaque chaussette a exactement une paire correspondante), quel est le meilleur moyen de les coupler efficacement avec un espace supplémentaire logarithmique? (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:

  • Une solution théorique générale pour un grand nombre de chaussettes.
  • Le nombre réel de chaussettes n’est pas très élevé, je ne crois pas que mon épouse et moi-même avons plus de 30 paires. (Et il est assez facile de faire la distinction entre mes chaussettes et les siennes; cela peut-il aussi être utilisé?)
  • Est-il équivalent au problème de la distinction des éléments ?

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

Et le plus souvent, il ne s'agit pas de n'importe quel temps libre, mais bien du matin , que vous pouvez passer au lit ou siroter votre café ou partir un peu plus tôt sans être pris dans la circulation.

Il est souvent bon de prendre du recul et de penser au problème.

Et il y a un moyen!

Trouvez une chaussette que vous aimez. Tenez compte de toutes les caractéristiques pertinentes: couleur dans différentes conditions d'éclairage, qualité et durabilité globales, confort dans différentes conditions climatiques et absorption des odeurs. Il est également important qu’ils ne perdent pas leur élasticité au stockage, de sorte que les tissus naturels sont bons et qu’ils doivent être disponibles dans un emballage plastique.

C'est mieux s'il n'y a pas de différence entre les chaussettes 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 trier les chaussettes est approximativement une opération O (M), où M représente le nombre de places dans votre maison, que vous avez jonchées de chaussettes, idéalement petit nombre constant.

Si vous avez choisi une paire de fantaisie avec une chaussette gauche et une chaussette différente, effectuez un tri complet au godet pour les pieds gauche et droit, prenez O (N + M), où N est le nombre de chaussettes et M est identique à 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 une recherche à l'aveugle est N / 2 + 1, ce qui devient un cas astronomique pour un nombre de N raisonnable. Cela peut être accéléré avec une image avancée algorithmes de reconnaissance et heuristiques, lors de la numérisation de la pile de chaussettes non triées avec Mk1 Eyeball .

Ainsi, un algorithme permettant d’obtenir une efficacité d’appariement de chaussettes O (1) (en supposant une chaussette symétrique) est le suivant:

  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 que vous vous déplaciez dans des climats plus chauds sans que vous ayez besoin de porter des chaussettes. Si vous êtes jeune, vous pouvez également estimer le temps qu'il faudra avant que nous ayons tous des robots pour trier les chaussettes chez nous, et le problème dans son ensemble deviendra inutile.

  2. Vous devez savoir comment commander votre chaussette sélectionnée en vrac, combien cela coûte et comment elle est livrée.

  3. Commandez les chaussettes!

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

Une étape 3 alternative consisterait à comparer les coûts d’achat d’un même montant de chaussettes peut-être moins chères, quelques paires à la fois, au fil des ans, et à ajouter le coût du tri des chaussettes, mais croyez-moi, l’achat en gros coûte moins cher! En outre, la valeur des chaussettes stockées augmente au même rythme que l’inflation du prix des actions, ce qui est supérieur à ce que vous obtiendrez avec de nombreux investissements. Là encore, il y a aussi un coût de stockage, mais les chaussettes ne prennent vraiment pas beaucoup de place sur l'étagère supérieure d'un placard.

Problème résolu. Donc, procurez-vous simplement de nouvelles chaussettes, jetez / donnez vos anciennes chaussettes et vivez heureux pour toujours après avoir su que vous économisiez de l'argent et du temps tous les jours pour le reste de votre vie.


Ce que je fais, c'est que je prenne la première chaussette et la pose (par exemple sur le bord du bol de la lessive). Ensuite, je prends une autre chaussette et vérifie si elle est identique à la première chaussette. Si c'est le cas, je les enlève tous les deux. Si ce n'est pas le cas, je le pose à côté de la première chaussette. Ensuite, je prends la troisième chaussette et la compare aux deux premières (si elles sont toujours là). Etc.

Cette approche peut être assez facilement implémentée dans un tableau, en supposant que "retirer" 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 obtenir un tableau contenant toutes les chaussettes disposées par paires dans le tableau.

En supposant que la seule opération pour les chaussettes consiste à comparer l'égalité, cet algorithme reste fondamentalement un algorithme n 2 , bien que je ne connaisse pas le cas moyen (je n'ai jamais appris à calculer cela).

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

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


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

Les humains peuvent vaincre les algorithmes de la CPU en utilisant le fait que "trouver une paire correspondante" peut être une opération pour un ensemble pas trop gros.

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 vie réelle et je le trouve très efficace. L'inconvénient est qu'il nécessite une surface plane, mais elle est généralement abondante.


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

Donc, le hachage serait suffisant (et plus rapide).

  1. Pour chaque couleur de chaussettes, formez une pile . Parcourez toutes les chaussettes de votre panier d’entrée et répartissez-les sur les piles de couleurs .
  2. Parcourez chaque pile et répartissez-la selon une autre métrique (modèle, par exemple) dans le deuxième ensemble de piles.
  3. Appliquez ce schéma de manière récursive jusqu'à ce que toutes les chaussettes soient réparties sur de très petites piles que vous pouvez traiter visuellement immédiatement

Ce type de partitionnement récursif de hachage est en fait effectué par SQL Server lorsqu'il doit hacher la jointure ou l'agrégat de 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 à des quantités arbitraires de données et à plusieurs processeurs de manière linéaire.

Vous n'avez pas besoin de partitionnement récursif si vous pouvez trouver une clé de distribution (clé de hachage) fournissant suffisamment de compartiments pour que chaque compartiment soit 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 répartir en 10 PairID % 10 selon PairID % 10 (le dernier chiffre).

Le meilleur partitionnement réel auquel 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. (Un cuboid 3D fonctionnerait aussi, mais ce n'est pas très pratique.)

Mettre à jour:

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

  1. La stratégie de parallélisation la plus simple consiste à faire en sorte que plusieurs travailleurs prennent dans le panier d’entrée et mettent les chaussettes sur les piles. Cela ne fait qu'aggraver les choses: imaginez 100 personnes qui se disputent 10 piles. Les coûts de synchronisation (qui se traduisent par des collisions de mains et des communications humaines) détruisent l'efficacité et la rapidité (voir la loi universelle sur l'évolutivité !). Est-ce sujet aux impasses ? Non, car chaque travailleur n'a besoin d'accéder qu'à une pile à la fois. Avec un seul "verrou", il ne peut y avoir d'impasse. Livelocks pourrait être possible selon la façon dont les humains coordonnent l'accès aux piles. Ils peuvent simplement utiliser un backoff aléatoire, comme les cartes réseau le font physiquement pour déterminer quelle carte peut accéder exclusivement au fil réseau. Si cela fonctionne pour les NICs , il devrait également fonctionner pour les humains.
  2. Il évolue presque indéfiniment si chaque ouvrier a son propre ensemble de piles . Les travailleurs peuvent ensuite prendre de gros morceaux de chaussettes dans le panier d’entrée (très peu de conflits, car ils le font rarement) et n’ont pas besoin de se synchroniser lors de la distribution des chaussettes (car ils ont des piles de fils locaux). À la fin, tous les travailleurs doivent syndiquer leurs ensembles de piles. Je crois que cela peut être fait en O (journal (nombre de travailleurs * piles par travailleur)) si les travailleurs forment un arbre d'agrégation .

Qu'en est-il du problème de la distinction des éléments ? Comme le précise l'article, le problème de la distinction des éléments peut être résolu en O(N) . C’est la même chose pour le problème des chaussettes (également O(N) , si vous n’avez besoin que d’une étape de distribution (j’ai proposé plusieurs étapes uniquement parce que les humains calculent mal - une étape suffit si vous distribuez sur md5(color, length, pattern, ...) , c’est-à-dire un hachage parfait de tous les attributs)).

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

Bien que les sorties ne soient pas exactement les mêmes (dans un cas, il s'agit simplement d'un booléen. Dans l'autre cas, les paires de chaussettes), les complexités asymptotiques sont les mêmes.


La limite théorique est O (n) car vous devez toucher chaque chaussette (à moins que certaines ne soient déjà associées d'une manière ou d'une autre).

Vous pouvez obtenir O (n) avec le tri de base . Il vous suffit de choisir des attributs pour les compartiments.

  1. D'abord, vous pouvez choisir (le sien, le mien) - séparez-les en 2 piles,
  2. utilisez ensuite des couleurs (vous pouvez choisir n'importe quel ordre de couleurs, par exemple, alphabétiquement par nom de couleur) - séparez-les 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 longueur de la chaussette,
  4. puis texture, ....

Si vous pouvez choisir un nombre limité d'attributs, mais suffisamment d'attributs pouvant identifier chaque paire de manière unique, vous devez le faire en O (k * n), qui est O (n) si nous pouvons considérer que k est limité.


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

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

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

Utilisez le tri de base . Ce n'est que temps linéaire, car 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 sont en paire. Choisissez l'un des algorithmes de tri basés sur la comparaison O(n log n) .

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


Vous essayez de résoudre le mauvais problème.

Solution 1: Chaque fois que vous mettez des chaussettes sales dans votre panier à linge, nouez-les en un petit noeud. De cette façon, vous ne ferez aucun tri après le lavage. Pensez-y comme à l'enregistrement d'un index dans une base de données Mongo. Un peu de travail à venir pour des économies d’ordinateur par la suite.

Solution 2: Si c'est l'hiver, vous n'avez pas besoin de porter des chaussettes assorties. Nous sommes des programmeurs. Personne n'a besoin de savoir, tant que cela fonctionne.

Solution 3: Répartissez le travail. Vous souhaitez exécuter un processus CPU aussi complexe de manière asynchrone, sans bloquer l'interface utilisateur. Prenez cette pile de chaussettes et mettez-les dans un sac. Ne cherchez une paire que lorsque vous en avez besoin. De cette façon, la quantité de travail nécessaire est beaucoup moins perceptible.

J'espère que cela t'aides!


Approche du monde réel:

Le plus rapidement possible, retirez les chaussettes de la pile non triée une par une et placez-les en piles devant vous. Les piles doivent être disposées assez efficacement dans l'espace, avec toutes les chaussettes orientées dans la même direction; le nombre de piles est limité par la distance que vous pouvez facilement atteindre. Le choix d’une pile sur laquelle placer une chaussette doit être effectué - le plus rapidement possible - en la plaçant sur une pile de chaussettes apparemment semblables; les erreurs occasionnelles de type I (mettre une chaussette sur une pile à laquelle elle n'appartient pas) ou de type II (mettre une chaussette dans sa propre pile lorsqu'il existe une pile de chaussettes semblables) peuvent être tolérées - le facteur le plus important étant la rapidité. Une fois que toutes les chaussettes sont empilées, parcourez rapidement les piles de chaussettes multiples en créant et en retirant les paires (elles se dirigent vers le tiroir). S'il y a des chaussettes non appariées dans la pile, réempilez-les au mieux (dans la contrainte la plus rapide possible). Lorsque toutes les piles de chaussettes multiples ont été traitées, faites correspondre les chaussettes appariées restantes qui ne l'ont pas été en raison d'erreurs de type II. Whoosh, vous avez terminé - et j'ai beaucoup de chaussettes et je ne les lave pas avant qu'une grande partie ne soit sale. Autre remarque pratique: je bascule le haut d’une des chaussettes sur l’autre, tirant parti de leurs propriétés élastiques, afin qu’elles restent ensemble tout en étant transportées dans le tiroir et dans le tiroir.


Considérons une table de hachage de taille 'N'.

Si nous supposons une distribution normale, alors le nombre estimé d'insertions avec au moins une chaussette mappée sur un seau est NlogN (c'est-à-dire que tous les seaux sont pleins)

J'avais dérivé cela dans le cadre d'un autre casse-tête, mais je serais heureux de pouvoir me tromper. Voici mon article de blog sur le même

Laissons "N" correspondre à une limite supérieure approximative du nombre de couleurs / motifs de chaussettes uniques que vous avez.

Une fois que vous avez une collision (ou une allumette), retirez simplement cette paire de chaussettes. Répétez la même expérience avec le prochain lot de chaussettes NlogN. La beauté de ceci est que vous pouvez faire des comparaisons parallèles avec NlogN (résolution de collision) à cause du fonctionnement de l'esprit humain. :-)


J'ai fini d'associer mes chaussettes tout de suite et j'ai trouvé que la meilleure façon de le faire était la suivante:

  • Choisissez l'une des chaussettes et rangez-la (créez un «seau» pour cette paire)
  • Si la suivante est la paire de la précédente, placez-la dans le compartiment existant, sinon créez-en une nouvelle.

Dans le pire des cas, cela signifie que vous aurez n / 2 compartiments différents et que vous aurez n-2 déterminations sur le compartiment contenant la paire de chaussettes actuelle. Évidemment, cet algorithme fonctionne bien si vous n’avez que quelques paires; Je l'ai fait avec 12 paires.

Ce n'est pas si scientifique, mais ça marche bien :)


J'ai proposé une autre solution qui ne promettrait pas moins d'opérations, ni moins de consommation de temps, mais il faudrait essayer de voir si elle peut constituer une heuristique suffisamment bonne pour réduire la consommation de temps dans les énormes séries de paires de chaussettes.

Conditions préalables: Il n'y a aucune garantie qu'il existe les mêmes chaussettes. S'ils sont de la même couleur, cela ne signifie pas qu'ils ont la même taille ou le même motif. Les chaussettes sont mélangées au hasard. Il peut y avoir un nombre impair de chaussettes (il en manque, nous ne savons pas combien). Préparez-vous à mémoriser une variable "index" et définissez-la sur 0.

Le résultat aura une ou deux piles: 1. "apparié" et 2. "manquant"

Heuristique:

  1. Trouvez la chaussette la plus distinctive.
  2. Trouvez sa correspondance.
  3. S'il n'y a pas de correspondance, placez-la sur la pile "manquante".
  4. Répétez de 1. jusqu'à ce qu'il n'y ait plus de chaussettes plus distinctives.
  5. S'il y a moins de 6 chaussettes, aller à 11.
  6. Paire à l'aveugle toutes les chaussettes à son voisin (ne pas l'emballer)
  7. Trouvez toutes les paires appariées, emballez-la et déplacez les paires emballées vers une pile "appariée"; S'il n'y a pas eu de nouvelle correspondance - incrémenter "index" de 1
  8. Si "index" est supérieur à 2 (la valeur peut dépendre du nombre de chaussettes car avec un plus grand nombre de chaussettes, les chances de les appairer à l'aveuglette sont moindres), passez à 11
  9. Mélangez le reste
  10. Aller à 1
  11. Oubliez "index"
  12. Choisir une chaussette
  13. Trouver sa paire
  14. S'il n'y a pas de paire pour la chaussette, déplacez-la vers la pile "manquante"
  15. Si une correspondance est trouvée, associez-la et placez-la dans la pile "correspondante"
  16. S'il y a encore plus d'une chaussette, passez à 12
  17. S'il n'en reste qu'un, passez à 14
  18. Sourire satisfait :)

En outre, il pourrait être ajouté vérifier pour les chaussettes endommagées aussi, comme si l'enlèvement de ceux-ci. Il pourrait être inséré entre 2 et 3 et entre 13 et 14.

J'ai hâte de connaître vos expériences ou vos corrections.


Les chaussettes, qu'elles soient réelles ou à structure de données analogue, seraient fournies par paires.

La réponse la plus simple est avant de permettre la séparation de la paire. Une structure de données unique pour la paire aurait dû être initialisée, laquelle contiendrait un pointeur sur la chaussette gauche et droite, permettant ainsi de référencer les chaussettes directement ou via leur paire. Une chaussette peut également être étendue pour contenir un pointeur sur son partenaire.

Cela résout tout problème d'appariement informatique en le supprimant avec une couche d'abstraction.

En appliquant la même idée au problème pratique de l’association de chaussettes, la réponse évidente est la suivante: ne laissez jamais vos chaussettes être non appariées. Les chaussettes sont fournies par paire, placées dans le tiroir par paire (peut-être en les agglomérant ensemble), portées par paire. Mais le point où le désappariement est possible est dans la laveuse. Il suffit donc d'un mécanisme physique qui permette aux chaussettes de rester ensemble et d'être lavées efficacement.

Il y a deux possibilités physiques:

Pour un objet "paire" gardant un pointeur sur chaque chaussette, nous pourrions avoir un sac en tissu que nous utilisons pour garder les chaussettes ensemble. Cela semble être une surcharge massive.

Mais pour que chaque chaussette garde une référence à l'autre, il existe une solution simple: un popper (ou un "bouton-poussoir" si vous êtes américain), tels que:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Ensuite, tout ce que vous faites est de casser vos chaussettes juste après les avoir enlevées et de les mettre dans votre panier à linge. Une fois encore, vous avez supprimé le problème de la nécessité de coupler vos chaussettes avec une abstraction physique du concept de "paire".


Chaque fois que vous prenez une chaussette, mettez-la au même endroit. Ensuite, la prochaine chaussette que vous prenez, si elle ne correspond pas à la première chaussette, placez-la à côté de la première. Si c'est le cas, il y a une paire. De cette façon, le nombre de combinaisons importées n'a pas vraiment d'importance et il n'y a que deux possibilités pour chaque chaussette que vous prenez - soit une correspondance est déjà présente dans votre gamme de chaussettes, soit ce n'est pas le cas, ce qui signifie que vous ajoutez-le à une place dans le tableau.

Cela signifie également que vous n'aurez probablement jamais toutes vos chaussettes dans le tableau, car les chaussettes seront retirées à mesure qu'elles sont appariées.


Créez une table de hachage qui sera utilisée pour les chaussettes incomparables, en utilisant le motif en tant que hachage. Itérez sur les chaussettes une à une. Si la chaussette a un motif correspondant dans la table de hachage, retirez-la de la table et faites-en une paire. Si la chaussette n'a pas de correspondance, placez-la dans la table.


J'espère pouvoir apporter quelque chose de nouveau à ce problème. J'ai remarqué que toutes les réponses négligent le fait qu'il existe deux points où vous pouvez effectuer un prétraitement , sans ralentir les performances globales de votre blanchisserie.

En outre, nous n’avons pas besoin de supposer un grand nombre de chaussettes, même pour les familles nombreuses. Les chaussettes sont sorties du tiroir et sont usées, et elles sont jetées dans un endroit (peut-être une corbeille) où elles restent avant d'être lavées. Bien que je n'appellerais pas dit bin une pile LIFO, je dirais qu'il est prudent de supposer que

  1. les gens jettent leurs deux chaussettes à peu près dans la même zone de la corbeille,
  2. la poubelle n'est pas randomisée à aucun moment, et donc
  3. tout sous-ensemble prélevé à partir du haut de cette corbeille contient généralement les deux chaussettes d'une paire.

Étant donné que toutes les machines à laver que je connais sont de taille limitée (quel que soit le nombre de chaussettes à laver) et que la randomisation se produit dans la machine à laver, quel que soit le nombre de chaussettes que nous avons, nous avons toujours de petits sous-ensembles qui ne contiennent presque pas singletons.

Nos deux étapes de prétraitement consistent à "mettre les chaussettes sur la corde à linge" et "à retirer les chaussettes de la corde à linge", ce que nous devons faire pour obtenir des chaussettes non seulement propres, mais également sèches. Comme avec les machines à laver, les cordes à linge sont finies, et je suppose que nous avons toute la partie de la ligne où nous mettons nos chaussettes en vue.

Voici l'algorithme pour put_socks_on_line ():

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

Ne perdez pas votre temps à déplacer des chaussettes ou à chercher le meilleur match, tout cela devrait être fait en O (n), ce dont nous aurions également besoin pour les mettre sur la ligne non triées. Les chaussettes ne sont pas encore appariées, nous avons seulement plusieurs clusters de similarité sur la ligne. Il est utile que nous ayons un nombre limité de chaussettes ici, car cela nous aide à créer de "bons" clusters (par exemple, s'il n'y a que des chaussettes noires dans l'ensemble des chaussettes, le groupement par couleurs ne serait pas la solution.)

Voici l'algorithme pour take_socks_from_line ():

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

Je tiens à souligner que pour améliorer la vitesse des étapes restantes, il est sage de ne pas choisir au hasard la chaussette suivante, mais de prendre séquentiellement chaussette après chaussette dans chaque groupe. Les deux étapes de prétraitement ne prennent pas plus de temps que de simplement mettre les chaussettes sur la ligne ou dans le panier, ce que nous devons faire quoi qu'il en soit, cela devrait donc grandement améliorer les performances de la blanchisserie.

Après cela, il est facile de faire l’algorithme de partitionnement de hachage. Habituellement, environ 75% des chaussettes sont déjà appariées, ce qui me laisse un très petit sous-ensemble de chaussettes, et ce sous-ensemble est déjà (quelque peu) en cluster (je n'introduis pas beaucoup d'entropie dans mon panier après les étapes de prétraitement). Une autre chose est que les grappes restantes ont tendance à être assez petites pour pouvoir être manipulées en une fois. Il est donc possible de sortir toute une grappe du panier.

Voici l'algorithme pour sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

Après cela, il ne reste que quelques chaussettes. C’est là que j’introduis dans le système des chaussettes non encore appariées et que je traite les chaussettes restantes sans algorithme particulier - les chaussettes restantes sont très peu nombreuses et peuvent être traitées visuellement très rapidement.

Pour toutes les chaussettes restantes, je suppose que leurs homologues ne sont toujours pas lavées et les rangez pour la prochaine itération. Si vous enregistrez une croissance de chaussettes non appariées au fil du temps (une "fuite de chaussette"), vous devriez vérifier votre poubelle - elle pourrait être randomisée (avez-vous des chats qui y dorment?)

Je sais que ces algorithmes reposent sur de nombreuses hypothèses: une corbeille qui agit comme une sorte de pile LIFO, une machine à laver limitée et normale et une corde à linge normale et limitée - mais cela fonctionne toujours avec un très grand nombre de chaussettes.

À propos du parallélisme: tant que vous jetez les deux chaussettes dans le même bac, vous pouvez facilement paralléliser toutes ces étapes.


Le problème du tri de vos n paires de chaussettes est O (n) . Avant de les jeter dans le panier à linge , vous devez enfiler celui de gauche dans celui de droite. En les retirant, vous coupez le fil et placez chaque paire dans votre tiroir - 2 opérations sur n paires, donc O (n).

Maintenant, la question suivante est simplement de savoir si vous faites votre propre linge et que votre femme fait le sien. C’est un problème probable dans un domaine de problèmes totalement différent . :)


Ma solution ne correspond pas exactement à vos besoins, car elle nécessite formellement de l' O(n)espace "supplémentaire". Cependant, compte tenu de mes conditions, il est très efficace dans mon application pratique. Ainsi, je pense que cela devrait être intéressant.

Combiner avec une autre tâche

La condition particulière dans mon cas est que je n’utilise pas de sèche-linge, je suspends simplement mes vêtements à un sèche-linge ordinaire. Suspendre des étoffes nécessite des O(n)opérations (d'ailleurs, je considère toujours le problème d' emballage de bacs ici) et le problème, de par sa nature, nécessite un espace "supplémentaire" linéaire. Quand je prends une nouvelle chaussette dans le seau, je tente de la suspendre à côté de sa paire si la paire est déjà suspendue. Si c'est une chaussette d'une nouvelle paire, je laisse un peu d'espace à côté.

Oracle Machine, c'est mieux ;-)

De toute évidence, il faut un peu plus de travail pour vérifier si la chaussette assortie est déjà suspendue quelque part et cela rendrait la solution O(n^2)avec un coefficient approximatif 1/2pour un ordinateur. Mais dans ce cas, le "facteur humain" est en fait un avantage - je peux généralement très rapidement (presque O(1)) identifier la chaussette correspondante si elle était déjà accrochée (probablement une cachette imperceptible dans le cerveau est impliquée) - considérez-la comme une sorte de "oracle" limité comme dans Oracle Machine ;-) Nous, les humains, avons dans certains cas ces avantages par rapport aux machines numériques ;-)

L'avoir presque O(n)!

Ainsi, en reliant le problème d’appariement des chaussettes au problème des toiles suspendues, j’obtiens un O(n)«espace supplémentaire» gratuit, et une solution à peu près O(n)dans le temps, qui nécessite juste un peu plus de travail que de simples toiles suspendues et qui permet d’accéder immédiatement à une paire complète de vêtements. chaussettes même dans un très mauvais lundi matin ... ;-)


Prenez une première chaussette et placez-la sur une table. Maintenant, choisissez une autre chaussette; si elle correspond à la première cueillie, placez-la sur la première. Sinon, placez-le sur la table à une petite distance de la première. Choisissez une troisième chaussette; si elle correspond à l'une des deux précédentes, placez-la sur celles-ci ou placez-la à une petite distance de la troisième. Répétez l'opération jusqu'à ce que vous ayez ramassé toutes les chaussettes.


Voici comment je le fais réellement, pour p paires de chaussettes ( n = 2p chaussettes individuelles):

  • Prenez une chaussette au hasard dans la pile.
  • Pour la première chaussette, ou si toutes les chaussettes précédemment sélectionnées ont été appariées, placez simplement la chaussette dans le premier "emplacement" d'un "tableau" de chaussettes non appariées devant vous.
  • Si vous avez sélectionné une ou plusieurs chaussettes non appariées, comparez votre chaussette actuelle à toutes les chaussettes non appariées du tableau.
    • Il est possible de séparer les chaussettes en classes ou types généraux (blanc / noir, cheville / crew, athlétique / robe) lors de la construction de votre matrice et de "forer en bas" pour comparer uniquement les points similaires.
    • Si vous trouvez une correspondance acceptable, associez les deux chaussettes et supprimez-les du tableau.
    • Si vous ne le faites pas, placez la chaussette actuelle dans le premier emplacement libre de la matrice.
  • Répétez avec chaque chaussette.

Le pire scénario de ce schéma est que chaque paire de chaussettes est suffisamment différente pour correspondre exactement et que les n / 2 premières chaussettes que vous choisissez sont toutes différentes. Ceci est votre scénario O (n 2 ) et il est extrêmement improbable. Si le nombre de types de chaussettes uniques t est inférieur au nombre de paires p = n / 2 et si les chaussettes de chaque type sont suffisamment similaires (généralement en termes d'usure), toute chaussette de ce type peut être associée à n'importe quel type de chaussette. d’autre part, comme je l’ai indiqué plus haut, le nombre maximal de chaussettes que vous aurez à comparer est t , après quoi le prochain que vous tirerez seracorrespondre à l'une des chaussettes non appariées. Ce scénario est beaucoup plus probable dans le tiroir à chaussettes moyen que dans le pire des cas et réduit la complexité du pire des cas à O (n * t), où t << n en général .


Voici une limite inférieure Omega (n log n) dans le modèle basé sur la comparaison. (La seule opération valide consiste à comparer deux chaussettes.)

Supposons que vous sachiez que vos 2n chaussettes sont disposées de la manière suivante:

p 1 p 2 p 3 ... p n p f (1) p f (2) ... p f (n)

où f est une permutation inconnue de l'ensemble {1,2, ..., n}. Sachant cela ne peut pas rendre le problème plus difficile. Il y en a! sorties possibles (correspondances entre la première et la seconde moitié), ce qui signifie que vous avez besoin d'une comparaison log (n!) = Omega (n log n) Ceci peut être obtenu en triant.

Puisque vous êtes intéressé par les liens avec le problème de distinction d'éléments: il est plus difficile de prouver l'Omega (n log n) lié à la distinction d'éléments, car la sortie est binaire oui / non. Ici, la sortie doit être une correspondance et le nombre de sorties possibles suffit pour obtenir une limite décente. Cependant, il existe une variante liée à la distinction d'éléments. Supposons que vous receviez 2n chaussettes et demandez-vous si elles peuvent être jumelées de manière unique. Vous pouvez obtenir une réduction de ED en envoyant (un 1 , un 2 , ..., un n ) à (un 1 , un 1 , un 2 , un 2 , ..., un n , un n ). (Entre parenthèses, la preuve de la dureté de l’ED est très intéressante,via la topologie .)

Je pense qu’il devrait exister une limite Omega (n 2 ) pour le problème initial si vous autorisez uniquement les tests d’égalité. Mon intuition est la suivante: considérons un graphique dans lequel vous ajoutez une arête après un test et expliquez que si le graphique n'est pas dense, la sortie n'est pas déterminée de manière unique.







matching