Comment puis-je associer efficacement des chaussettes à partir d'un velours?

3914

Hier, je jumelais les chaussettes du linge propre et j'ai compris que ma façon de faire n'était 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 itérer 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 entendu venu à l'esprit pour aboutir à une solution O (NlogN).

Le hachage ou d'autres solutions non en place ne sont pas une option, car je ne suis pas en mesure 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 npaires de chaussettes contenant des 2néléments (supposons que chaque chaussette a exactement une paire assortie), quelle est la meilleure façon de les associer efficacement avec un espace supplémentaire jusqu'à 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 si grand, je ne crois pas que mon conjoint et moi en ayons plus de 30 paires. (Et il est assez facile de faire la distinction entre mes chaussettes et les siennes; cela peut-il également être utilisé?)
  • Est-il équivalent au problème de la distinction des éléments ?
amit
la source
448
J'utilise le principe du trou de pigeon pour en associer exactement un à la pile de linge. J'ai 3 couleurs différentes de chaussettes (rouge, bleu et vert) et 2 paires de chaque couleur. Je prends 4 chaussettes à chaque fois et je compose toujours une paire et je me mets au travail.
Srinivas
59
Encore un autre principe du pigeon: si vous prenez un sous-ensemble de n / 2 +1 chaussettes, il doit y avoir au moins une paire dans ce sous-ensemble.
wildplasser
40
Grande question! Vous pourriez être intéressé par mon article sur un problème connexe, qui est une discussion sur la probabilité de retirer deux chaussettes assorties de la pile: blogs.msdn.com/b/ericlippert/archive/2010/03/22/…
Eric Lippert
337
Pourquoi ne pas engendrer un enfant et waitpidpour que, en tant que parent, vous ne triiez même pas de chaussettes vous-même?
Mxyk
137
J'ai résolu ce problème en ne possédant que des chaussettes blanches jusqu'aux genoux. Ils correspondent tous. Je pourrais simplement attraper deux chaussettes au hasard dans la pile et elles correspondraient. Je simplifie encore le problème en NE jumelant PAS les chaussettes. J'ai un tiroir à chaussettes dans lequel je jette simplement toutes mes chaussettes, sans paire. J'en prends deux au hasard dans le tiroir chaque matin. Je l'ai simplifié jusqu'à O (0). Impossible de faire plus simple que ça. :)
Lee

Réponses:

2450

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 pour l'égalité .

Le hachage serait donc suffisant (et plus rapide).

  1. Pour chaque couleur de chaussettes, formez un tas . Parcourez toutes les chaussettes de votre panier d'entrée et répartissez-les sur les piles de couleur .
  2. Itérer sur chaque pile et la distribuer par 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 réparti toutes les chaussettes sur de très petites piles que vous pouvez traiter visuellement immédiatement

Ce type de partitionnement de hachage récursif est en fait effectué par SQL Server lorsqu'il a besoin de joindre ou de regrouper des hachages sur d'énormes ensembles de données. Il distribue son flux d'entrée de génération dans de nombreuses partitions indépendantes. Ce schéma s'adapte à des quantités arbitraires de données et à plusieurs processeurs linéairement.

Vous n'avez pas besoin de partitionnement récursif si vous pouvez trouver une clé de distribution (clé de hachage) qui fournit 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 seaux selon PairID % 10(le dernier chiffre).

La meilleure partition du monde réel à laquelle je peux 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 d'un accès aléatoire O (1) aux piles. (Un cuboïde 3D fonctionnerait également, mais ce n'est pas très pratique.)


Mise à jour:

Et le 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 le panier d'entrée et de mettre les chaussettes sur les piles. Cela ne fait que grandir - imaginez 100 personnes se battant sur 10 piles. Les coûts de synchronisation (se manifestant par des collisions avec les mains et la communication humaine) détruisent l'efficacité et l'accélération (voir la loi universelle sur l'évolutivité !). Est-ce sujet à des blocages ? Non, car chaque travailleur n'a besoin d'accéder qu'à une seule pile à la fois. Avec un seul "verrou", il ne peut pas y avoir d'impasse. Les livelocks pourraient être possibles selon la façon dont les humains coordonnent l'accès aux piles. Ils pourraient simplement utiliser une interruption aléatoirecomme les cartes réseau, faites cela au niveau physique pour déterminer quelle carte peut accéder exclusivement au câble réseau. Si cela fonctionne pour les cartes réseau , il devrait également fonctionner pour les humains.
  2. Il évolue presque indéfiniment si chaque travailleur a son propre jeu 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 ils n'ont pas du tout besoin de se synchroniser lors de la distribution des chaussettes (car ils ont des piles locales). À la fin, tous les travailleurs doivent syndiquer leurs ensembles de pieux. 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 .

Qu'en est-il du problème de distinction des éléments ? Comme l'indique 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 n'avez besoin que d'une seule étape de distribution (j'ai proposé plusieurs étapes uniquement parce que les humains sont mauvais dans les calculs - une étape suffit si vous distribuez 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), donc nous avons atteint la 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.

usr
la source
72
C'est exactement ce que je fais! Je fais des piles en fonction du style de l'ouverture de la chaussette (je n'ai que du blanc), ce qui me donne suffisamment de "seaux" pour correspondre rapidement à chacun d'eux.
Scott Chamberlain
30
J'ai essayé cela avec mes chaussettes (j'ai facilement plus de 30 paires) et l'homme c'est RAPIDE. Un problème que j'ai trouvé, c'est quand je ne peux pas avoir un algorithme de hachage suffisamment bon (j'ai beaucoup de chaussettes blanches sans aucun motif), donc cela devient difficile. Dans ce cas, quelle serait la meilleure façon de procéder?
NothingsImpossible
56
@NothingsImpossible, c'est comme ça que les attaques par collision de hachage se sentent pour un pauvre serveur web! Les chaussettes blanches se distinguent-elles par un attribut? Il doit y avoir quelque chose sur lequel vous pouvez les distribuer. Sinon, vous pourriez simplement former des paires arbitrairement.
usr
37
Il s'agit d'un Radix Sort, qui, je suis d'accord, est la bonne réponse. @MarkPeters Je ne pense pas que vous ayez besoin d'une table de recherche. Un seul passage linéaire sur les chaussettes peut convertir les chaussettes en vecteurs numériques, ce qui rend trivial le mappage du "segment de chaussette" en seau. Les chaussettes peuvent être liées aux vecteurs avec une chaîne de sorte que vous n'avez pas besoin d'un autre passage linéaire à la fin.
Pointy
49
Un gars avec qui j'étais allé à l'université avait en fait des PairID. Il a été cousu sur chaque paire de chaussettes avec du fil: 1, 2, 3, 4 ...
Ryan Lundy
579

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

Les humains peuvent gagner les algorithmes 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 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.

dpc.ucore.info
la source
229
à mesure que le nombre de chaussettes augmente, le SIMD humain ne devient pas meilleur qu'un CPU.
Lie Ryan
25
La meilleure réponse, l'OMI. Bien qu'il soit amusant et intelligent (et approprié pour SO) de réduire un problème quotidien à un algorithme informatique, il est beaucoup plus logique d'utiliser le pouvoir de résolution de l'œil / cerveau de l'homme pour un ensemble aussi petit que ~ 60 chaussettes.
drug_user841417
13
@LieRyan Si les chaussettes sont uniformément réparties, vous finirez par remarquer une paire dans un ensemble de chaussettes suffisamment petit en raison du paradoxe de l'anniversaire (sauf si vous pouvez distinguer les couleurs avec une précision arbitraire, ce dont je doute), de sorte que le goulot d'étranglement ici ne serait pas l'algorithme de correspondance des couleurs humaines, mais l'étape de propagation.
Thomas
13
@ dpc.ucore.info Non, car ils ont différents motifs de manchette tissés, longueurs de manchette, longueurs globales et nuances de noir (ma femme me blesserait probablement physiquement pour cette dernière).
Christian
200
Vous feriez mieux d'espérer avoir un nombre pair de chaussettes, sinon vous allez plier des chaussettes pendant longtemps ...
Patrick James McDougle
258

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

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

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

Utilisez le tri radix . Il s'agit uniquement d'un temps linéaire car aucune comparaison n'est requise.

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 par 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 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.

Terry Li
la source
9
> Cela pourrait prendre encore plus de temps que la recherche séquentielle, qui nécessite en théorie un temps quadratique. Oui, c'est pourquoi je déteste faire ça, peut-être que je devrais jeter toutes mes chaussettes et commencer par le cas 1.
Nils
57
l'inconvénient d'avoir toutes les chaussettes identiques est qu'elles ont tendance à vieillir à des taux différents. Donc, vous finissez toujours par essayer de les assortir en fonction de leur usure. (ce qui est plus difficile que le simple appariement par motif)
DDC
119
Le problème d'avoir 60 paires de chaussettes identiques "car cela facilite le jumelage" est qu'il donne aux gens l'impression que vous travaillez avec des ordinateurs.
Steve Ives
13
Le cas 1 n'est pas un temps constant lorsqu'une opération est impliquée, comme le pliage de paires ensemble. Dans ce cas, c'est le temps linéaire avec le plus petit facteur constant (dont la preuve est laissée en exercice au lecteur). On ne peut pas prendre le même temps en pliant une paire et un seau plein de chaussettes. Cependant, il évolue linéairement. Selon la loi d'Amdahl, il a une accélération illimitée, ignorant les frais généraux. Selon la loi de Gustafson, vous pouvez plier autant de paires qu'il en faut pour plier une paire avec suffisamment d'ouvriers (dont le montant est laissé comme exercice pour le lecteur), en ignorant les frais généraux.
2013
8
@PauloMadeira Le tri est à temps constant - il suffit de prendre la pile et de la mettre dans votre tiroir. La seule opération dans ce cas est de mettre les chaussettes sur vos pieds, ce qui est également constant. Les performances sont obtenues par l'exécution différée du port de la chaussette, éventuellement avec un certain sacrifice dans l'espace (l'espace consommé des chaussettes non pliées est plus grand que plié). Je soutiens que cela en vaut la peine; Je perds habituellement cet argument avec ma femme.
Travis
157

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

  • étape 1) jetez toutes vos chaussettes existantes

  • étape 2) allez chez Walmart et achetez-les par paquets de 10 - n paquets de blanc et m paquets de noir. Pas besoin d'autres couleurs dans la vie de tous les jours.

Pourtant, de temps en temps, je dois recommencer (chaussettes perdues, chaussettes endommagées, etc.), et je déteste jeter trop souvent de bonnes chaussettes (et j'aurais souhaité qu'ils continuent à vendre la même référence de chaussettes!), Alors j'ai récemment pris une approche différente.

Réponse algorithmique:

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

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

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

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

  • Recherchez maintenant une correspondance (correspondance des motifs visuels - les humains sont bons avec une petite pile) à l'intérieur des cinq que vous avez dessinés, si vous n'en trouvez pas, puis ajoutez-la à vos cinq.

  • Continuez à choisir des chaussettes au hasard dans la pile et comparez-les à vos chaussettes 5 + 1 pour un match. À mesure que votre pile augmente, cela réduira vos performances mais augmentera vos chances. Plus vite.

N'hésitez pas à noter la formule pour calculer le nombre d'échantillons à prélever pour une chance de correspondance 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 ndes paires similaires (environ 10, donnez ou prenez les perdues) de mchaussettes blanches en forme. Vous pouvez maintenant estimer la taille de ma pile de stocks :-)

BTW , j'ai trouvé que la somme des coûts de transaction du 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 à lier les chaussettes, et il y a aussi un retour marginal décroissant (c'est-à-dire que vous continuez à chercher ces deux ou trois chaussettes qui se trouvent quelque part dans le linge et dont vous avez besoin pour finir de faire correspondre vos chaussettes et vous perdez du temps là-dessus).

guylhem
la source
25
Upvote pour la réponse «non algorithmique». C'est exactement ce que je fais et cela fonctionne à merveille. Le problème de remplacement n'est pas un problème si vous faites pivoter votre stock de chaussettes en plaçant des chaussettes lavées à l'arrière et en tirant de l'avant du tiroir le matin. Toutes les chaussettes s'usent uniformément. Lorsque je commence à remarquer une certaine usure sur une, je mets sur la liste de courses pour remplacer complètement cette classe entière de chaussettes. Pour les vieilles chaussettes, je donne le meilleur 20% à Goodwill (attaché dans un sac d'épicerie pour qu'elles ne se mélangent pas) et jette le reste. Vous ne perdez pas de chaussettes, à ce stade, les 80% n'ont plus que 6 mois.
FastAl
2
BTW (1) Le fait de lier vos chaussettes a pour conséquence que l'élastique est stocké étiré et qu'il échouera beaucoup plus rapidement. Limiter les types de chaussettes uniques que vous avez rend la reliure non collée. (2) Un inconvénient de limiter les chaussettes uniques est que, pour les personnes ayant certains problèmes de mode, la méthode peut ne pas convenir.
FastAl
3
Je suis venu ici spécialement pour poster votre réponse "non algorithmique". Comme dans la vraie informatique, la plupart des gens n'accordent jamais assez d'attention aux données et à leur structure.
bkconrad
J'utilise cette approche algorithmique tous les matins et ça marche comme un charme! De plus, j'ai mis des chaussettes usées dans une autre pile pour les jeter plus tard (malheureusement, elles parviennent à retrouver la pile d'origine avant de trouver le temps de la jeter).
Donatas Olsevičius
3
«N paquet de blanc et m paquets de noir. Pas besoin d'autres couleurs dans la vie de tous les jours »Une bonne règle standard pour une sélection facile des chaussettes est qu'elles doivent correspondre à la couleur de votre pantalon ou à la couleur de votre ceinture. Pour cette raison, les couleurs les plus couramment utilisées seront probablement le noir, le bleu, le gris et un peu de brun. Il est difficile de croire qu'il faut de nombreuses chaussettes blanches.
Andrea Lazzarotto
106

Ce que je fais, c'est que je prends la première chaussette et que je la pose (disons, sur le bord du bol à linge). Ensuite, je prends une autre chaussette et vérifie si c'est la même chose que la première chaussette. Si c'est le cas, je les supprime tous les deux. Si ce n'est pas le cas, je la 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 vous retrouver avec un tableau qui a toutes les chaussettes 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 algorithme n 2 , bien que je ne connaisse pas le cas moyen (jamais appris à calculer cela).

Le tri améliore bien sûr l'efficacité, en particulier dans la vie réelle où vous pouvez facilement "insérer" une chaussette entre deux autres chaussettes. En informatique, la même chose pourrait être obtenue 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 les mêmes en fonction des critères de tri, mais pas de la même paire).

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

Vilx-
la source
7
C'est aussi ce que je fais (notez que si vous laissez simplement des espaces, les inserts sont également O (1)), mais cela évolue mal avec un nombre théoriquement élevé de chaussettes.
Mooing Duck
15
se balance mal avec un grand nombre théoriquement de types de chaussettes
Steven Lu
@StevenLu - comme je l'ai dit - c'est n * n ou nLogn, selon que vous le triez ou non. Il évolue donc à peu près aussi mal que n'importe quel algorithme de tri. Si vous voulez plus vite, numérotez-les et utilisez le tri radix.
Vilx-
Il s'agit essentiellement de stocker des chaussettes trouvées mais non assorties dans une recherche basée sur le hachage. Avec un hachage idéal, c'est O (n), mais si vous avez suffisamment de chaussettes stockées pour que le hachage commence à dégénérer, il devient plus complexe en conséquence.
Jon Hanna
3
quelle valeur l'insertion d'une chaussette entre 2 autres chaussettes apporte-t-elle à l'objectif d'associer des chaussettes? il n'y a pas de cardinalité des chaussettes. : -x
JoeBrockhaus
60

Cela pose la mauvaise question. La bonne question à poser est la suivante: pourquoi passe-je du temps à trier les chaussettes? Combien cela coûte-t-il chaque année, lorsque 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, il est matin temps libre, que vous pourriez dépenser au lit, ou en sirotant votre café, ou en laissant un peu plus tôt et ne pas être pris dans le trafic.

Il est souvent bon de prendre du recul et de réfléchir à un moyen de contourner le 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é globale et durabilité, confort dans différentes conditions climatiques et absorption des odeurs. Il est également important qu'ils ne perdent pas leur élasticité au stockage, les tissus naturels sont donc bons et doivent être disponibles dans un emballage plastique.

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

Si vous avez choisi une paire fantaisie avec des chaussettes gauche et droite différentes, faire un tri complet du seau vers les seaux du 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 des itérations moyennes pour trouver la première paire, mais le pire des cas pour trouver une paire avec recherche aveugle est N / 2 + 1, ce qui devient un cas astronomiquement improbable pour un N raisonnable. Cela peut être accéléré en utilisant une image avancée algorithmes de reconnaissance et heuristique, lors de la numérisation de la pile de chaussettes non triées avec Mk1 Eyeball .

Ainsi, un algorithme pour atteindre l'efficacité d'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 que vous vous dirigiez vers des climats plus chauds sans avoir à porter de chaussettes. Si vous êtes jeune, vous pouvez également estimer le temps qu'il faudra avant que nous ayons tous des robots de tri des chaussettes dans nos maisons, et tout le problème devient sans importance.

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

  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 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 sur parole: acheter en vrac est moins cher! De plus, les chaussettes dans le stockage augmentent en valeur au rythme de l'inflation du cours des actions, ce qui est plus que ce que vous obtiendriez sur de nombreux investissements. Là encore, il y a aussi des frais 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. Alors, procurez-vous de nouvelles chaussettes, jetez / donnez vos anciennes et vivez heureux pour toujours en sachant que vous économisez de l'argent et du temps chaque jour pour le reste de votre vie.

hyde
la source
Une offre à vie (en supposant 75 ans) de chaussettes (en supposant que vous épuisiez 4 paires / mois, ce qui fait 3600 paires) prendrait (en supposant qu'une nouvelle paire de chaussettes prenne 20 pouces cubes) un total de 1 1/2 verges cubes. C'est une énorme quantité d'espace. En supposant qu'ils vous le livrent dans une boîte qui est à peu près un cube, cette caisse sera d'environ 3 pieds 4 pouces de côté.
AJMansfield
2
@AJMansfield préoccupation valable. Cependant, je ne suis pas d'accord avec quelques-uns de vos chiffres. Je prendrais une période de temps de seulement 40 ans (25 ... 65) (temps entre ne pas vivre chez les parents / dortoir / etc et prendre sa retraite, voir ci-dessus). De plus, je pense qu'une paire prend plus comme 0,5x4x6 pouces dans son emballage d'origine. Ces chiffres font baisser un peu votre estime de l'espace!
hyde
L'étape 4 est inutilement inutile, -1.
Dan Bechard
2
Guide pour ceux qui pourraient être déroutés par les mesures d'AJMansfield, une traduction en métrique: »prendrait (en supposant qu'une nouvelle paire de chaussettes occupe 327 cm³) un total de 1,14 m³. C'est une énorme quantité d'espace. En supposant qu'ils vous le livrent dans une boîte qui est à peu près un cube, cette caisse sera d'environ 1,04 m de côté. »
Joey
Comment une question basée sur la curiosité peut-elle être "la mauvaise question"? Classic StackOverflow ...
Timmmm
52

La limite théorique est O (n) car vous devez toucher chaque chaussette (sauf si certaines sont déjà appariées d'une manière ou d'une autre).

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

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

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

andredor
la source
3
Les chaussettes viennent souvent en 4 paquets et plus, car c'est moins cher, mais cela les rend également indiscernables. Pour contrer cela, ma femme coud une petite marque sur chaque nouvelle paire de chaussettes que j'achète. La marque est d'une couleur différente pour chaque paire, ou d'une forme différente, si elle manque de couleurs. Avec cette approche, vous n'avez même pas besoin d'un ensemble limité d'attributs. Cousez simplement un numéro unique sur chaque paire. :) Pour des points supplémentaires, utilisez le binaire.
Vilx-
29
@ Vilx- POURQUOI?!? N'est-ce pas tout le fait qu'ils soient indiscernables?
flup
2
@flup - Je pense que le but est de vendre en gros lots. :) Quant à moi, cela aide à les porter par paires. Sinon, je peux me retrouver avec trois chaussettes très usées et une toute neuve. Un peu idiot.
Vilx-
13
Je ne suis pas d'accord avec le calcul de O (n). Qu'est-ce que $ k $? $ k $ est le nombre d'attributs. Je dirais que $ k $ est $ O (log n) $ car il doit être suffisant pour identifier de manière unique chaque paire. Si vous avez 2 paires (noir et blanc), alors la couleur ($ k = 1, n = 2 $) suffit. Si vous avez une paire de noir, courte; une paire de noir, longue; une paire de blancs, courts; et une paire de blancs, longs - alors $ k = 2, n = 4 $. Alors si on limite $ k $, on limite en même temps $ n $. Si nous allons limiter $ n $, alors le calcul de la commande n'a plus de sens.
emory
3
@emory, je pense que vous cherchez le backtick, pas le $personnage, pour que vos trucs ressemblent au code-y.
Xymostech
33

Comme solution pratique:

  1. Faites rapidement des tas de chaussettes facilement reconnaissables. (Dites par couleur)
  2. Triez rapidement chaque pile et utilisez la longueur de la chaussette pour comparer. En tant qu'humain, vous pouvez prendre une décision assez rapide quelle chaussette utiliser pour partitionner ce qui évite le pire des cas. (Vous pouvez voir plusieurs chaussettes en parallèle, utilisez-les à votre avantage!)
  3. Arrêtez de trier les piles lorsqu'elles ont atteint un seuil auquel vous êtes à l'aise pour trouver instantanément des paires de points et des chaussettes impairables

Si vous avez 1000 chaussettes, avec 8 couleurs et une distribution moyenne, vous pouvez faire 4 piles de 125 chaussettes en c * n temps. Avec un seuil de 5 chaussettes, vous pouvez trier chaque pile en 6 manches. (Compter 2 secondes pour jeter une chaussette sur la pile droite, cela vous prendra un peu moins de 4 heures.)

Si vous n'avez que 60 chaussettes, 3 couleurs et 2 sortes de chaussettes (la vôtre / celle de votre femme), vous pouvez trier chaque pile de 10 chaussettes en 1 fois (seuil de nouveau = 5). (Compter 2 secondes cela vous prendra 2 min).

Le tri initial des seaux accélérera votre processus, car il divise vos n chaussettes en k seaux dans le c*ntemps, de sorte que vous n'aurez plus qu'à c*n*log(k)travailler. (Ne tenant pas compte du seuil). Donc, dans l'ensemble, vous faites du n*c*(1 + log(k))travail, où c est le moment de jeter une chaussette sur une pile.

Cette approche sera favorable par rapport à n'importe quelle c*x*n + O(1)méthode à peu près aussi longtemps que log(k) < x - 1.


En informatique, cela peut être utile: nous avons une collection de n choses , un ordre sur elles (longueur) et aussi une relation d'équivalence (informations supplémentaires, par exemple la couleur des chaussettes). La relation d'équivalence nous permet de faire une partition de la collection d'origine, et dans chaque classe d'équivalence, notre ordre est toujours maintenu. Le mappage d'une chose à sa classe d'équivalence peut être effectué dans O (1), donc seul O (n) est nécessaire pour affecter chaque élément à une classe. Nous avons maintenant utilisé nos informations supplémentaires et pouvons procéder de n'importe quelle manière pour trier chaque classe. L'avantage est que les ensembles de données sont déjà considérablement plus petits.

La méthode peut également être imbriquée, si nous avons plusieurs relations d'équivalence -> faire des piles de couleurs, que dans chaque partition de pile sur la texture, que trier sur la longueur. Toute relation d'équivalence qui crée une partition avec plus de 2 éléments de même taille apportera une amélioration de la vitesse par rapport au tri (à condition que nous puissions directement affecter une chaussette à sa pile), et le tri peut se produire très rapidement sur des ensembles de données plus petits.

Samuel
la source
3
Optimisation humaine: je dirais qu'en tant qu'humain, pour l'étape 2, vous devez plonger les chaussettes dans un ordre grossièrement ascendant, puis répéter avec une granularité de plus en plus fine jusqu'à ce qu'elles soient triées, un peu comme le tri de la coquille. Ce serait beaucoup plus rapide pour un humain (estimation visuelle) qu'une approche basée sur un échange de comparaison.
AndrewC
28

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

Solution 1: Chaque fois que vous mettez des chaussettes sales dans votre panier à linge, attachez-les en un petit nœud. De cette façon, vous n'aurez pas à faire de tri après le lavage. Pensez-y comme enregistrer un index dans une base de données Mongo. Un peu de travail à venir pour des économies de CPU à l'avenir.

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

Solution 3: répartissez le travail. Vous souhaitez effectuer un processus CPU aussi complexe de manière asynchrone, sans bloquer l'interface utilisateur. Prenez ce tas 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 qu'il faut est beaucoup moins perceptible.

J'espère que cela t'aides!

Nikolay Dyankov
la source
5
Attacher des chaussettes (ou des vêtements) en un nœud réduit la capacité de la laveuse à laver les vêtements et rend leur déliement beaucoup plus difficile à porter. La solution 2 rend la maintenance plus difficile à mesure que la situation évolue; après 6 mois, lorsque vous avez besoin de deux chaussettes noires à porter avec une paire de shorts et de baskets, 6 mois de faire tout ce qui va rendre la recherche de cette paire dans le même état (sale / propre, usure similaire) beaucoup moins probable. La solution 3 est moins "asynchrone" et plus directe "paresseuse"; faites le travail minimum dont vous avez besoin exactement quand vous en avez besoin.
KeithS
Re: solution 2: Les gens sauront que je ne porte pas de chaussettes assorties car ils les verront dans mes Birks :)
Bob Probst
@BobProbst Oui, mais vos collègues programmeurs porteront également des chaussettes inégalées avec Birks et seront donc heureux de constater qu'ils ne sont pas les seuls.
Francesco Pasa
27

Cette question est en réalité profondément philosophique. Au fond, il s'agit de savoir si le pouvoir des gens de résoudre des problèmes (le «wetware» de notre cerveau) est équivalent à ce qui peut être accompli par des algorithmes.

Un algorithme évident pour le tri des chaussettes est:

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

Maintenant, l'informatique dans ce problème concerne les étapes

  1. "si s s'associe avec une chaussette t en N". À quelle vitesse pouvons-nous nous «souvenir» de ce que nous avons vu jusqu'à présent?
  2. "supprimer t de N" et "ajouter s à N". Combien coûte le suivi de ce que nous avons vu jusqu'à présent?

Les êtres humains utiliseront diverses stratégies pour les réaliser. La mémoire humaine est associative , quelque chose comme une table de hachage où les ensembles de caractéristiques des valeurs stockées sont associés aux valeurs correspondantes elles-mêmes. Par exemple, le concept de «voiture rouge» correspond à toutes les voitures rouges dont une personne est capable de se souvenir. Quelqu'un avec une mémoire parfaite a une cartographie parfaite. La plupart des gens sont imparfaits à cet égard (et la plupart des autres). La carte associative a une capacité limitée. Les mappages peuvent biper exister dans diverses circonstances (une bière de trop), être enregistré par erreur ("Je pensais que son nom était Betty, pas Nettie"), ou ne jamais être écrasé même si nous observons que la vérité a changé ("la voiture de papa" évoque "Orange Firebird" alors que nous savions qu'il l'avait échangé contre la Camaro rouge).

Dans le cas des chaussettes, un rappel parfait signifie que regarder une chaussette sproduit toujours la mémoire de son frère t, y compris suffisamment d'informations (où elle se trouve sur la planche à repasser) pour la localiser ten temps constant. Une personne ayant une mémoire photographique accomplit à la fois 1 et 2 en un temps constant sans faute.

Quelqu'un dont la mémoire n'est pas parfaite peut utiliser quelques classes d'équivalence de bon sens basées sur des fonctionnalités à sa disposition pour suivre: taille (papa, maman, bébé), couleur (verdâtre, rougeâtre, etc.), motif (argyle, uni, etc.) , style (foot, genou, etc.). Ainsi, la planche à repasser serait divisée en sections pour les catégories. Cela permet généralement de localiser la catégorie en temps constant par la mémoire, mais une recherche linéaire dans la catégorie "bucket" est alors nécessaire.

Quelqu'un sans mémoire ni imagination (désolé) gardera simplement les chaussettes dans une pile et fera une recherche linéaire de la pile entière.

Un monstre ordonné pourrait utiliser des étiquettes numériques pour les paires comme quelqu'un l'a suggéré. Cela ouvre la porte à un ordre total, qui permet à l'humain d'utiliser exactement les mêmes algorithmes que nous pourrions utiliser avec un CPU: recherche binaire, arbres, hachages, etc.

Le "meilleur" algorithme dépend donc des qualités du logiciel / matériel / logiciel qui le fait fonctionner et de notre volonté de "tricher" en imposant un ordre total aux paires. Un «meilleur» méta- algorithme consiste certainement à embaucher le meilleur trieur de chaussettes au monde: une personne ou une machine qui peut acquérir et stocker rapidement un énorme ensemble N d’ensembles d’attributs de chaussette dans une mémoire associative 1-1 avec recherche en temps constant, insérer, et supprimez. Des personnes et des machines comme celle-ci peuvent être achetées. Si vous en avez une, vous pouvez associer toutes les chaussettes en temps O (N) pour N paires, ce qui est optimal. Les balises de commande totales vous permettent d'utiliser le hachage standard pour obtenir le même résultat avec un ordinateur humain ou matériel.

Gène
la source
D'accord, c'est mieux, même si c'est encore tout à fait faux ... cette question n'est pas à ce sujet. Que la thèse de Church-Turing soit correcte ou non, les humains et nos ordinateurs peuvent trier les chaussettes. (La réalité est que, les êtres humains, étant des entités hautement finies, ont beaucoup moins de puissance de calcul que les machines de Turing ... et il en va de même pour nos ordinateurs, mais les limites sont différentes.)
Jim Balter
Je ne suis pas d'accord. Bien sûr, n'importe lequel de nos ordinateurs actuels est essentiellement et d'énormes DFA (différences d'E / S modulo) plutôt qu'une MT. Cependant, tout appareil analogique, comme notre corps, est capable d'émuler une bande infinie. Nous n'avons pas encore de caractérisation utile de la façon dont nos esprits calculent.
Gene
Pas de bande infinie pour les humains ou autres appareils physiques car rien dans le cerveau humain n'a une résolution infinie, ni ne pourrait le faire. Cela aiderait également à apprendre certaines neurosciences. En tout cas, il n'y avait pas de question philosophique profonde ici, quel que soit votre désir d'en injecter une. Mais croyez ce que vous voudrez ... ce n'est pas le lieu pour ce genre de débat et je l'ai eu trop de fois auparavant. Mais je suis toujours amusé par des gens qui peuvent à peine résoudre les problèmes les plus simples (c'est nous tous) en imaginant qu'ils sont équivalents à la MT.
Jim Balter
22

Coût: Déplacement des chaussettes -> élevé, recherche / recherche de chaussettes en ligne -> petit

Ce que nous voulons faire, c'est réduire le nombre de déplacements et compenser avec le nombre de recherches. En outre, nous pouvons utiliser l'environnement multithrédé de l'Homo Sapiens pour contenir plus de choses dans le cache de descision.

X = vôtre, Y = vos conjoints

De la pile A de toutes les chaussettes:

Choisissez deux chaussettes, placez la chaussette X correspondante sur la ligne X et la chaussette Y sur la ligne Y à la prochaine position disponible.

Faites jusqu'à ce que A soit vide.

Pour chaque ligne X et Y

  1. Choisissez la première chaussette en ligne, recherchez le long de la ligne jusqu'à ce qu'elle trouve la chaussette correspondante.

  2. Mettez dans la ligne de chaussettes finie correspondante.

  3. Facultatif Pendant que vous recherchez la ligne et que la chaussette actuelle que vous regardez est identique à la précédente, effectuez l'étape 2 pour ces chaussettes.

Facultativement, à l'étape 1, vous prenez deux chaussettes de cette ligne au lieu de deux, car la mémoire cache est suffisamment grande, nous pouvons rapidement identifier si l'une des chaussettes correspond à la chaussette actuelle sur la ligne que vous observez. Si vous avez la chance d'avoir trois bras, vous pouvez éventuellement analyser trois chaussettes en même temps étant donné que la mémoire du sujet est suffisamment grande.

Faites jusqu'à ce que X et Y soient vides.

Terminé

Cependant, comme cela a une complexité similaire à celle du tri par sélection, le temps nécessaire est beaucoup moins important en raison des vitesses d'E / S (déplacement des chaussettes) et de la recherche (recherche de la ligne pour une chaussette).

1 ----- 1
la source
22

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

Supposons que vous sachiez que vos chaussettes 2n sont disposées de cette façon:

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}. Le savoir ne peut pas rendre le problème plus difficile. Il y en a n! sorties possibles (correspondances entre la première et la seconde moitié), ce qui signifie que vous avez besoin de comparaisons log (n!) = Omega (n log n). Ceci peut être obtenu par tri.

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

Je pense qu'il devrait y avoir un Omega (n 2 ) lié au problème d'origine si vous autorisez uniquement les tests d'égalité. Mon intuition est la suivante: considérons un graphique dans lequel vous ajoutez un bord après un test, et faites valoir que si le graphique n'est pas dense, la sortie n'est pas déterminée de manière unique.

sdcvvc
la source
19

Voici comment je le fais, 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 choisies précédemment ont été jumelées, placez simplement la chaussette dans la première "fente" d'un "tableau" de chaussettes non appariées devant vous.
  • Si vous avez une ou plusieurs chaussettes non appariées sélectionnées, comparez votre chaussette actuelle à toutes les chaussettes non appariées de la matrice.
    • Il est possible de séparer les chaussettes en classes ou types généraux (blanc / noir, cheville / équipage, athlétique / robe) lors de la construction de votre gamme, et "drill-down" pour comparer uniquement à données comparables.
    • Si vous trouvez une correspondance acceptable, assemblez les deux chaussettes et retirez-les du tableau.
    • Si vous ne le faites pas, placez la chaussette actuelle dans le premier emplacement ouvert de la baie.
  • Répétez avec chaque chaussette.

Le pire des cas de ce schéma est que chaque paire de chaussettes est suffisamment différente pour qu'elle corresponde 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 uniques de chaussettes t est inférieur au nombre de paires p = n / 2 et que les chaussettes de chaque type sont suffisamment semblables (généralement en termes liés à l'usure) pour que toute chaussette de ce type puisse être associée à n'importe quelle autre, alors comme je l'ai déduit ci-dessus, le nombre maximum de chaussettes que vous devrez comparer est t , après quoi la prochaine 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 cas à O (n * t) où généralement t << n .

KeithS
la source
1
C'est probablement assez proche de mon processus mental. J'ai une couche supplémentaire d'optimisation de pré-tri. Mes chaussettes athlétiques sont lavées avec les blancs et mes chaussettes habillées sont lavées avec des couleurs. Cela signifie que tant que je ne décharge pas deux charges de linge ensemble, mes chaussettes sont déjà regroupées par type. La charge blanche va très vite (beaucoup de chaussettes identiques) mais les chaussettes habillées prennent plus de temps. Autre astuce clé
libérer de la
17

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 dans un espace peu efficace, toutes les chaussettes pointant dans la même direction; le nombre de piles est limité par la distance que vous pouvez facilement atteindre. La sélection d'une pile sur laquelle mettre une chaussette devrait être - aussi rapidement que possible - en mettant une chaussette sur une pile de chaussettes apparemment semblables; l'erreur occasionnelle 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 y a un tas de chaussettes similaires) peut être tolérée - la considération la plus importante est la vitesse .

Une fois que toutes les chaussettes sont empilées, parcourez rapidement les piles multi-chaussettes en créant des paires et en les retirant (elles se dirigent vers le tiroir). S'il y a des chaussettes non assorties dans la pile, empilez-les à leur meilleur (dans la contrainte la plus rapide possible). Lorsque toutes les piles multi-chaussettes ont été traitées, faites correspondre les chaussettes restantes qui n'ont pas été appariées en raison d'erreurs de type II. Whoosh, vous avez terminé - et j'ai beaucoup de chaussettes et je ne les lave pas tant qu'une grande partie n'est pas sale. Autre remarque pratique: je retourne le haut d'une paire de chaussettes sur l'autre, profitant de leurs propriétés élastiques, pour qu'elles restent ensemble tout en étant transportées dans le tiroir et dans le tiroir.

Peter Mortensen
la source
15

D'après votre question, il est clair que vous n'avez pas beaucoup d'expérience réelle avec la lessive :). Vous avez besoin d'un algorithme qui fonctionne bien avec un petit nombre de chaussettes non appariables.

Jusqu'à présent, les réponses ne font pas bon usage de nos capacités de reconnaissance des formes humaines. Le jeu de Set fournit un indice sur la façon de bien faire: mettez toutes les chaussettes dans un espace à deux dimensions afin que vous puissiez à la fois bien les reconnaître et les atteindre facilement avec vos mains. Cela vous limite à une zone d'environ 120 * 80 cm environ. De là, sélectionnez les paires que vous reconnaissez et supprimez-les. Mettez des chaussettes supplémentaires dans l'espace libre et répétez. Si vous vous lavez pour les gens avec des chaussettes facilement reconnaissables (les petits enfants viennent à l'esprit), vous pouvez faire un tri radical en sélectionnant d'abord ces chaussettes. Cet algorithme ne fonctionne bien que lorsque le nombre de chaussettes simples est faible

Stephan Eggermont
la source
C'est généralement comme ça que je le fais. Fonctionne beaucoup mieux que d'itérer à travers toutes les chaussettes restantes à chaque fois.
yu_ominae
Belle approche et je pense qu'elle peut également être appliquée à de vrais problèmes CS. Pouvez-vous s'il vous plaît en ajouter un exemple (un problème CS où nous pourrions utiliser une approche similaire pour résoudre des problèmes)? De plus, comment cette solution évolue-t-elle pour des millions de chaussettes?
Amit
Je pense que c'est fondamentalement la même chose que l'autre réponse ici, stackoverflow.com/a/14423956 , du 20 janvier. Les deux +1. Le système de vision humaine est massivement parallèle.
Will Ness
15

Prenez une première chaussette et placez-la sur une table. Maintenant, choisissez une autre chaussette; s'il correspond au premier sélectionné, placez-le au-dessus du premier. Sinon, placez-le sur la table à une petite distance du premier. Choisissez une troisième chaussette; s'il correspond à l'un des deux précédents, placez-le au-dessus d'eux ou bien placez-le à une petite distance du troisième. Répétez jusqu'à ce que vous ayez ramassé toutes les chaussettes.

justinfay
la source
1
Ceci est la seule réponse valable. Tous les autres ne tiennent pas compte du fait que l'on passe le plus de temps à distinguer des chaussettes similaires (donc les regrouper toutes par leur apparence physique les rend encore pire).
entonio
Pour le plaisir, j'ai écrit cette méthode d'empilage des chaussettes dans un petit programme python gist.github.com/justinfay/53b574cf0a492f6795ef
Justin Fay
12

Afin de dire à quel point il est efficace d'appairer des chaussettes à partir d'une pile, nous devons d'abord définir la machine, car l'appariement ne se fait ni par une turing ni par une machine à accès aléatoire, qui sont normalement utilisées comme base pour une analyse algorithmique.

La machine

La machine est l'abstraction d'un élément du monde réel appelé être humain. Il est capable de lire depuis l'environnement via une paire d'yeux. Et notre modèle de machine est capable de manipuler l'environnement en utilisant 2 bras. Les opérations logiques et arithmétiques sont calculées à l'aide de notre cerveau (espérons-le ;-)).

Nous devons également considérer le temps d'exécution intrinsèque des opérations atomiques qui peuvent être effectuées avec ces instruments. En raison de contraintes physiques, les opérations qui sont effectuées par un bras ou un œil ont une complexité temporelle non constante. En effet, nous ne pouvons pas déplacer un tas de chaussettes sans fin avec un bras, ni un œil voir la chaussette supérieure sur un tas de chaussettes sans fin.

Cependant, la physique mécanique nous donne aussi quelques goodies. Nous ne sommes pas limités à déplacer au plus une chaussette avec un bras. Nous pouvons déplacer un couple entier d'entre eux à la fois.

Ainsi, selon l'analyse précédente, les opérations suivantes doivent être utilisées dans l'ordre décroissant:

  • opérations logiques et arithmétiques
  • lecture de l'environnement
  • modifications environnementales

Nous pouvons également utiliser le fait que les gens n'ont qu'une quantité très limitée de chaussettes. Une modification environnementale peut donc concerner toutes les chaussettes du velours.

L'algorithme

Voici donc ma suggestion:

  1. Répartissez toutes les chaussettes dans la pile sur le sol.
  2. Trouvez une paire en regardant les chaussettes au sol.
  3. Répétez de 2 jusqu'à ce qu'aucune paire ne puisse être faite.
  4. Répétez de 1 jusqu'à ce qu'il n'y ait plus de chaussettes sur le sol.

L'opération 4 est nécessaire, car lors de la répartition des chaussettes sur le sol, certaines chaussettes peuvent en cacher d'autres. Voici l'analyse de l'algorithme:

L'analyse

L'algorithme se termine avec une forte probabilité. Cela est dû au fait que l'on ne trouve pas de paires de chaussettes à l'étape numéro 2.

Pour l'analyse d'exécution suivante de l'association de npaires de chaussettes, nous supposons qu'au moins la moitié des 2nchaussettes ne sont pas masquées après l'étape 1. Dans le cas moyen, nous pouvons trouver des n/2paires. Cela signifie que la boucle de l'étape 4 est exécutée O(log n)fois. L'étape 2 est exécutée O(n^2)fois. On peut donc conclure:

  • L'algorithme implique O(ln n + n)des modifications environnementales (étape 1 O(ln n)plus la cueillette de chaque paire de chaussettes du sol)
  • L'algorithme implique O(n^2)des lectures environnementales de l'étape 2
  • L'algorithme implique O(n^2)des opérations logiques et arithmétiques pour comparer une chaussette avec une autre à l'étape 2

Nous avons donc une complexité d'exécution totale de l' O(r*n^2 + w*(ln n + n))endroit ret wdes facteurs pour les opérations de lecture et d'écriture environnementales respectivement pour une quantité raisonnable de chaussettes. Le coût des opérations logiques et arithmétiques est omis, car nous supposons qu'il faut une quantité constante d'opérations logiques et arithmétiques pour décider si 2 chaussettes appartiennent à la même paire. Cela peut ne pas être possible dans tous les scénarios.

SpaceTrucker
la source
1
c'est la même chose que stackoverflow.com/a/14423956 et stackoverflow.com/a/14468913 je pense.
Will Ness
@WillNess Yep, avec un peu plus d'explications
SpaceTrucker
12
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}
Tchad
la source
12

Je suis sorti avec une autre solution qui ne promettrait pas moins d'opérations, ni moins de consommation de temps, mais il faudrait essayer de voir si cela peut être une bonne heuristique suffisante pour fournir moins de temps dans une énorme série 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 (certaines manquent, nous ne savons pas combien). Préparez-vous à mémoriser une variable "index" et mettez-la à 0.

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

Heuristique:

  1. Trouvez la chaussette la plus distinctive.
  2. Trouvez sa correspondance.
  3. S'il n'y a pas de correspondance, mettez-le sur la pile "manquante".
  4. Répétez de 1. jusqu'à ce qu'il n'y ait plus de chaussettes distinctives.
  5. S'il y a moins de 6 chaussettes, passez à 11.
  6. Associez aveuglément toutes les chaussettes à son voisin (ne les emballez pas)
  7. Trouvez toutes les paires appariées, emballez-les et déplacez les paires emballées vers la pile "appariée"; S'il n'y avait pas de nouvelles correspondances - incrémenter "index" de 1
  8. Si "indice" est supérieur à 2 (cela peut dépendre de la valeur du nombre de chaussettes car avec un plus grand nombre de chaussettes, il y a moins de chance de les coupler à l'aveugle) passez à 11
  9. Mélangez le reste
  10. Allez à 1
  11. Oubliez "index"
  12. Choisissez une chaussette
  13. Trouvez sa paire
  14. S'il n'y a pas de paire pour la chaussette, déplacez-la sur la pile "manquante"
  15. Si une correspondance a été trouvée, associez-la, 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 au 14
  18. Sourire satisfait :)

En outre, il pourrait être ajouté une vérification des chaussettes endommagées également, comme si la suppression de celles-ci. Il pourrait être inséré entre 2 et 3, et entre 13 et 14.

J'ai hâte d'entendre parler de toute expérience ou correction.

Sasa
la source
Après avoir écrit cela, je l'utilise à chaque fois. Cela m'a aidé à devenir un peu plus efficace et le travail est moins ennuyeux maintenant.
Sasa
11

Lorsque je trie les chaussettes, je fais un tri approximatif par radix , en déposant des chaussettes à proximité d'autres chaussettes du même type de couleur / motif. Sauf dans le cas où je peux voir une correspondance exacte à / près de l'endroit où je suis sur le point de laisser tomber la chaussette, j'extrais la paire à ce moment-là.

Presque tous les autres algorithmes (y compris la réponse la mieux notée par usr ) trient, puis suppriment les paires. Je trouve qu'en tant qu'humain, il vaut mieux minimiser le nombre de chaussettes envisagées à la fois.

Je le fais en:

  1. Choisir une chaussette distinctive (tout ce qui attire mon attention en premier dans la pile).
  2. Commencer un tri radix à partir de cet emplacement conceptuel en tirant des chaussettes de la pile en fonction de la similitude avec celle-ci.
  3. Placez la nouvelle chaussette près de la pile actuelle, avec une distance basée sur la différence. Si vous vous retrouvez à mettre la chaussette sur une autre parce qu'elle est identique, formez-y la paire et retirez-la. Cela signifie que les comparaisons futures nécessitent moins d'efforts pour trouver le bon endroit.

Cela profite de la capacité humaine de correspondance floue en temps O (1), ce qui équivaut quelque peu à l'établissement d'une carte de hachage sur un appareil informatique.

En tirant d'abord sur les chaussettes distinctives, vous laissez un espace pour «zoomer» sur les caractéristiques qui sont moins distinctives, pour commencer.

Après avoir éliminé la couleur fluro, les chaussettes à rayures et les trois paires de chaussettes longues, vous pourriez vous retrouver avec des chaussettes principalement blanches grossièrement triées en fonction de leur port.

À un moment donné, les différences entre les chaussettes sont suffisamment petites pour que d'autres personnes ne remarquent pas la différence, et aucun effort supplémentaire n'est nécessaire.

Andrew Hill
la source
10

Chaque fois que vous prenez une chaussette, placez-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 n'a pas vraiment d'importance, et il n'y a que deux possibilités pour chaque chaussette que vous prenez - soit elle a une correspondance qui est déjà dans votre gamme de chaussettes, soit elle ne l'est pas, ce qui signifie que vous ajoutez-le à une place dans le tableau.

Cela signifie également que vous n'aurez presque certainement jamais toutes vos chaussettes dans le tableau, car les chaussettes seront retirées au fur et à mesure de leur correspondance.

trpt4him
la source
C'est ce que je fais ... O (n)
Pykler
2
@Pykler - C'est O (n) dans le meilleur des cas et O (n * n) dans le pire des cas.
Vilx-
2
C'est en supposant que vous ne pouvez pas créer un hachage entièrement unique dans votre esprit de toutes les chaussettes que vous avez déjà vues, ce qui pour moi est un O (1) pour correspondre à une chaussette que j'ai vue et précédemment placée dans l'attente du hachage
Pykler
10

Considérons une table de hachage de taille «N».

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

Je l'avais dérivé dans le cadre d'un autre casse-tête, mais je serais heureux d'avoir tort. Voici mon article de blog sur le même

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

Une fois que vous avez une collision (alias: 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 cela est que vous pourriez faire des comparaisons parallèles NlogN (résolution de collision) en raison de la façon dont fonctionne l'esprit humain. :-)

Arvind
la source
10

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

La réponse la plus simple est avant de permettre à la paire d'être séparée, une structure de données unique pour la paire aurait dû être initialisée qui contenait un pointeur vers la chaussette gauche et droite, permettant ainsi aux chaussettes d'être référencées 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.

Appliquant la même idée au problème pratique de l'appariement des chaussettes, la réponse apparente est: ne laissez jamais vos chaussettes être dissociées. Les chaussettes sont fournies par paire, placées dans le tiroir par paire (peut-être en les ballant ensemble), portées par paire. Mais le point où la dissociation est possible est dans la laveuse, donc tout ce qui est requis est un mécanisme physique qui permet aux chaussettes de rester ensemble et d'être lavées efficacement.

Il existe deux possibilités physiques:

Pour un objet «paire» qui garde 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 énorme.

Mais pour que chaque chaussette garde une référence à l'autre, il existe une solution intéressante: un popper (ou un 'bouton pression' si vous êtes américain), comme ceux-ci:

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

Ensuite, tout ce que vous faites est de mettre vos chaussettes en place juste après les avoir retirées et les mettre dans votre panier à linge, et encore une fois vous avez éliminé le problème de devoir associer vos chaussettes avec une abstraction physique du concept de `` paire ''.

mozboz
la source
Cela ne répond pas à la question, car la manipulation avec des données déjà appariées est facile, la question est de savoir quoi faire lorsque les données ne sont pas appariées et que vous souhaitez les associer.
2015
8

Si l'opération "déplacer" est assez coûteuse, et l'opération "comparer" est bon marché, et vous devez quand même déplacer l'ensemble dans un tampon où la recherche est beaucoup plus rapide que dans le stockage d'origine ... intégrez simplement le tri dans le champ obligatoire bouge toi.

J'ai trouvé que l'intégration du processus de tri en suspension pour sécher en fait un jeu d'enfant. Je dois quand même ramasser chaque chaussette, la suspendre (bouger) et cela ne me coûte rien de la suspendre à un endroit précis sur les cordes. Maintenant, juste pour ne pas forcer la recherche de tout le tampon (les cordes), je choisis de placer les chaussettes par couleur / nuance. Plus sombre à gauche, plus clair à droite, devant plus coloré, etc. Maintenant, avant de suspendre chaque chaussette, je regarde dans son "voisinage droit" si une assortie est déjà là - cela limite le "scan" à 2-3 autres chaussettes - et si c'est le cas , J'accroche l'autre juste à côté. Ensuite, je les roule en paires tout en les retirant des cordes, une fois sèches.

Maintenant, cela peut ne pas sembler très différent de la "formation de piles par couleur" suggérée par les meilleures réponses, mais d'abord, en ne choisissant pas des piles discrètes mais des plages, je n'ai aucun problème à classer si "violet" passe à "rouge" ou "bleu"; ça va juste entre. Et puis, en intégrant deux opérations (suspendre pour sécher et trier), le surcoût du tri pendant la suspension équivaut à 10% de ce que serait le tri séparé.

SF.
la source
Cette approche présente deux autres avantages: le séchage en ligne perd beaucoup moins de chaussettes IME que le sèche-linge, et le processus de tri peut être étendu au reste du linge, de sorte que (par exemple) toutes les serviettes sont proches les unes des autres pour être pliées. ligne et rangé et emmené directement à leur stockage. Il fonctionne également en deux passes à faible effort, remettant les vêtements et les retirant à nouveau.
cphlewis
8

J'ai fini d'appairer mes chaussettes en ce moment, et j'ai trouvé que la meilleure façon de le faire est la suivante:

  • Choisissez l'une des chaussettes et rangez-la (créez un `` seau '' pour cette paire)
  • Si le suivant est la paire du précédent, placez-le dans le compartiment existant, sinon créez-en un nouveau.

Dans le pire des cas, cela signifie que vous aurez n / 2 seaux différents, et vous aurez n-2 déterminations sur ce que le seau contient la paire de la chaussette 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 :)

maestro
la source
Il s'agit toujours d'un algorithme O (n ^ 2) car vous devez parcourir chaque compartiment à chaque fois que vous sortez une nouvelle chaussette. Mais, étant donné que même les chaussettes achetées dans le même lot présentent des différences mineures qui les rendent effectivement uniques par paire (ou même uniques), il n'y a pas de meilleure façon de toute façon
Semisonic
D'accord, mais mon algorithme suppose que l'humain fait l'appariement. Par conséquent, il y aura une sorte de cache dans votre esprit lorsque vous recherchez le compartiment correspondant, de sorte que vous n'avez pas vraiment besoin de parcourir les compartiments de toute façon. Je ne sais pas quel type de structure de données est construit pour ce mécanisme de mise en cache dans ma tête pendant le couplage.
maestro le
8

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

Combiner avec une autre tâche

La condition spéciale dans mon cas est que je n'utilise pas de sèche-linge, accrochez simplement mes chiffons sur un sèche-linge ordinaire. Suspendre des chiffons nécessite des O(n)opérations (au fait, je considère toujours l' emballage des poubelles problème d' bacs ici) et le problème de par sa nature nécessite un espace "supplémentaire" linéaire. Lorsque je prends une nouvelle chaussette dans le seau, j'essaie de l'accrocher à côté de sa paire si la paire est déjà accrochée. Si c'est une chaussette d'une nouvelle paire, je laisse un peu d'espace à côté.

Oracle Machine is Better ;-)

Cela nécessite évidemment un travail supplémentaire pour vérifier si la chaussette correspondante est déjà suspendue quelque part et cela rendrait la solution O(n^2)avec le coefficient environ 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 assortie si elle était déjà accrochée (probablement une mise en cache imperceptible dans le cerveau est impliquée) - considérez-la comme une sorte de "oracle" limité comme dans Oracle Machine ;-) Nous, les humains ont ces avantages sur les machines numériques dans certains cas ;-)

Je l'ai presque O(n)!

Reliant ainsi le problème de l'appariement des chaussettes au problème des tissus suspendus, j'obtiens O(n)gratuitement "de l'espace supplémentaire", et j'ai une solution qui est à peu près O(n)dans le temps, nécessite juste un peu plus de travail que les simples tissus suspendus et permet d'accéder immédiatement à une paire complète de chaussettes même dans un très mauvais lundi matin ... ;-)

wrzasa
la source
8

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 vos performances globales de lessive.

De plus, nous n'avons pas besoin d'assumer un grand nombre de chaussettes, même pour les familles nombreuses. Les chaussettes sont retirées du tiroir et sont portées, puis jetées dans un endroit (peut-être une poubelle) où elles restent avant d'être lavées. Bien que je n'appellerais pas ledit bac une pile LIFO, je dirais qu'il est sûr de supposer que

  1. les gens jettent leurs deux chaussettes à peu près dans la même zone de la poubelle,
  2. le bac n'est pas randomisé à aucun moment, et donc
  3. tout sous-ensemble pris du haut de ce bac 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 que vous devez laver), et la randomisation réelle se produit dans la machine à laver, peu importe le nombre de chaussettes que nous avons, nous avons toujours de petits sous-ensembles qui ne contiennent presque pas de singletons.

Nos deux étapes de prétraitement sont «mettre les chaussettes sur la corde à linge» et «retirer les chaussettes de la corde à linge», ce que nous devons faire, afin d'obtenir des chaussettes non seulement propres mais aussi sèches. Comme pour 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 la meilleure combinaison, tout cela devrait être fait en O (n), dont nous aurions également besoin pour les mettre sur la ligne sans tri. Les chaussettes ne sont pas encore appariées, nous n'avons que plusieurs groupes de similitudes sur la ligne. Il est utile que nous ayons un ensemble 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 de chaussettes, le regroupement par couleurs ne serait pas la voie à suivre)

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 dois souligner que pour améliorer la vitesse des étapes restantes, il est sage de ne pas choisir aléatoirement la prochaine chaussette, mais de prendre séquentiellement chaussette après chaussette de chaque cluster. 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 arrive, cela devrait donc améliorer considérablement les performances du linge.

Après cela, il est facile de faire l'algorithme de partitionnement de hachage. Habituellement, environ 75% des chaussettes sont déjà appariées, me laissant avec un très petit sous-ensemble de chaussettes, et ce sous-ensemble est déjà (quelque peu) groupé (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 suffisamment petites pour être manipulées en même temps, il est donc possible de retirer une grappe entière 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 plus que quelques chaussettes. C'est là que j'introduis des chaussettes non appariées dans le système et traite les chaussettes restantes sans algorithme spécial - 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és et les range 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 dorment là-dedans?)

Je sais que ces algorithmes prennent beaucoup d'hypothèses: une poubelle qui agit comme une sorte de pile LIFO, une machine à laver normale limitée et une corde à linge normale 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.

Philipp Flenker
la source
Les chaussettes ne sont que la métaphore de l'association d'objets arbitraires dans certaines bases de données.
2015
1
J'ai compris, je n'ai pas vu que tu étais l'auteur. Si vous vouliez une solution générique, vous auriez vraiment dû le dire. Quoi qu'il en soit, il n'y a rien de mal à prendre en compte les informations dont vous disposez, sauf si vous devez trouver une solution générale - renoncer à la réutilisabilité de la solution pourrait entraîner des performances considérablement meilleures. Dans ce cas, il est avantageux de considérer le cas d'utilisation et la base de données disponible dans son ensemble. Cependant, cette réponse spéciale à votre question spéciale a des problèmes avec des chaussettes d'aspect similaire, par exemple des chaussettes noires de différentes tailles, donc elle n'est pas applicable dans certains cas.
Philipp Flenker
1
De plus, vous n'avez pas obtenu> 2 000 votes positifs parce que vous avez posé une question sur le couplage d'objets arbitraires dans la base de données. Vous avez spécifiquement limité la question en raison de la nature même des chaussettes (que vous ne pouvez pas dupliquer, contrairement aux données), vous avez même encouragé à utiliser le fait que vous pouvez facilement distinguer vos chaussettes des chaussettes de votre conjoint. Si vous posez une question sur les chaussettes, ne vous attendez pas à ce que les réponses concernent les bases de données ;-)
Philipp Flenker
1
Il y a quelques hypothèses: une machine à laver normale, une corde à linge normale et le fait que vous jetiez les deux chaussettes dans le bac en même temps, ce qui signifie que dans la plupart des cas, les deux chaussettes sont dans la même machine et le nombre de les chaussettes restantes à trier sont donc petites. Mais comme vous vouliez vraiment une réponse sur le stockage d'objets arbitraires dans la base de données, est-il vraiment utile de discuter de ma solution plus avant?
Philipp Flenker
1
Comme je l'ai dit, je pense avoir répondu à tout ce que vous avez demandé, à l'exception du problème de la distinction des éléments, auquel d'autres personnes ont répondu. Je n'essaie pas d'être une putain ici, mais j'ai mis beaucoup d'efforts dans cette réponse il y a un certain temps, et je suis légèrement déçu que vous passiez maintenant en revue certaines des réponses et affirmiez qu'ils n'ont pas répondu à la question d'origine . Pourquoi ne laissez-vous pas tout le fil seul - c'est toujours une lecture intéressante, plus de 2 ans après que vous l'ayez posée?
Philipp Flenker
8

J'ai pris des mesures simples pour réduire mes efforts en un processus prenant du temps O (1).

En réduisant mes entrées à l'un des deux types de chaussettes (chaussettes blanches pour les loisirs, chaussettes noires pour le travail), je n'ai qu'à déterminer laquelle des deux chaussettes j'ai en main. (Techniquement, comme ils ne sont jamais lavés ensemble, j'ai réduit le processus à O (0).)

Un effort initial est nécessaire pour trouver des chaussettes souhaitables et acheter en quantité suffisante pour éliminer le besoin de vos chaussettes existantes. Comme je l'avais fait avant mon besoin de chaussettes noires, mon effort était minime, mais le kilométrage peut varier.

Un tel effort initial a été vu à plusieurs reprises dans un code très populaire et efficace. Les exemples incluent # DEFINE'ing pi à plusieurs décimales (d'autres exemples existent, mais c'est celui qui me vient à l'esprit en ce moment).

Scott Brickey
la source
7

Créez une table de hachage qui sera utilisée pour les chaussettes inégalées, en utilisant le motif comme hachage. Parcourez les chaussettes une par une. Si la chaussette a une correspondance de motif dans la table de hachage, retirez la chaussette de la table et faites une paire. Si la chaussette n'a pas de correspondance, mettez-la dans le tableau.

viper110110
la source
Comment ne pas le faire sur place, comme spécifiquement mentionné dans la question?
2015
7

Le problème du tri de vos n paires de chaussettes est O (n) . Avant de les jeter dans le panier à linge , vous enfilez celui de gauche vers celui de droite. En les retirant, vous coupez le fil et mettez 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 lessive et si votre femme fait la sienne. Il s'agit probablement d'un problème dans un domaine de problèmes entièrement différent . :)

Fred Mitchell
la source
Cela ne répond pas à la question, où les chaussettes ne sont qu'une métaphore.
2015
La question était de savoir comment appairer les chaussettes à partir d'une pile non appariée, et non comment éviter d'avoir à l'appairer.
Amit