Trier un tableau selon les éléments d'un autre ensemble

J'ai un tableau d'id de 

a1 = [1, 2, 3, 4, 5]

et j'ai un autre tableau d'objets avec des id dans un ordre aléatoire 

a2 = [(obj_with_id_5), (obj_with_id_2), (obj_with_id_1), (obj_with_id_3), (obj_with_id_4)]

Maintenant, j'ai besoin de trier a2 en fonction de l'ordre d'id dans a1. Donc a2 doit maintenant devenir: 

[(obj_with_id_1), (id_2), (id_3), (id_4), (id_5)]

a1 peut être [3, 2, 5, 4, 1] ou dans n'importe quel ordre, mais a2 doit correspondre à l'ordre de id dans a1.

Je fais comme ceci: 

a1.each_with_index do |id, idx|
  found_idx = a1.find_index { |c| c.id == id }
  replace_elem = a2[found_idx]
  a2[found_idx] = a2[idx]
  a2[idx] = replace_elem
end

Mais c'est toujours susceptible de s'exécuter en O(n^2) si l'ordre des éléments de a2 est exactement l'inverse de a1. Quelqu'un peut-il me dire de la façon la plus efficace de tri a2?

InformationsquelleAutor Ari53nN3o | 2012-08-14
  1. 26
    hash_object = objects.each_with_object({}) do |obj, hash| 
  hash[obj.object_id] = obj
end

[1, 2, 3, 4, 5].map { |index| hash_object[index] }
#=> array of objects in id's order

    Je crois que le temps d'exécution O(n)

    • Je crois que ce serait O(n^2). le tri est O(n), mais l'étape de préparation ferait il n^2
    • Je ne suis pas d'accord, pour construire une table de hachage nécessite O(n), ici en.wikipedia.org/wiki/Hash_table
    • Oui, la construction de la table de hachage est O(n) fois. Et le tri est O(n) fois. Si vous avez 2xO(n)... hmmm... ce serait moins de n^2. Je corrige la position des mains. bonne prise!
    • Vous n'êtes pas à corriger, 2xO(n) O(n) pour n.
    • Oui, vous avez raison, je vais d'accord avec vous pour une deuxième fois.
    • La première étape semble même que l'utilisation de hash_object = objects.index_by(&:object_id)
    • Mais la manière la plus rapide algo de tri est en O(nlogn). Comment il peut être O(n)? ont u viens de créer un plus rapide algo? Sa grande si vous avez à partager avec le monde entier.
    • Il est O(n), mais ne pas faire ce qui est demandé -- elle va revenir [nil, nil, nil, nil, nil] à moins que le object_ids se trouvent être les numéros 1 à 5. Pour le faire fonctionner, vous avez besoin pour obtenir le object_ids et de les trier, ce qui ne sera pas mieux que objects.index_by(&:object_id). Aussi, il n'est pas nécessaire pour expliquer le O(n) demande ici, mais note que le O(n log n) limite inférieure s'applique uniquement à la comparaison de toutes sortes.
    • Notez que la recherche de hachage est de ~O(1), c'est pourquoi la recherche de l'étape se comporte comme O(n), mais: - Cela va prendre un supplément de O(n) mémoire - étape de Construction augmenteront graduellement de hachage de taille (sauf si vous avez déjà réserver cette salle) et l'augmentation de hachage de taille est d'environ O(n), en faisant étape de création de quelque chose comme O(nlog(n)) (hachages utilisé pour augmenter la taille de façon exponentielle, c'est pourquoi l'augmentation de l'opération se fera comme log(n) fois) de toute façon, cela semble être la meilleure option, mais attention, il semble qu'il utilise O(nlog(n)) ops et O(n) supplément de mémoire
    • donc O(2n)? Pourquoi importe-t-il-qui se soucie vraiment de big-O de notation?

    InformationsquelleAutor megas
  2. 73

    Je serais surpris si quelque chose est beaucoup plus rapide que le moyen le plus évident:

    a2.sort_by{|x| a1.index x.id}
    • en supposant que a1 est triée (et c'est le problème stmt) et le récipient que vous utilisez pour a1 peut profiter du fait que a1 est triée puis je suis d'accord ce serait plus rapide que O(n^2).
    • Pas de a1 à trier n'est pas un avantage, je ne suis pas sûr pourquoi vous pourriez penser que. De cette façon, est rapide car il est intégré. En essayant de battre intégré sort_by semble une perte de temps pour moi.
    • a1 triées est un avantage. Si elle est triée puis l'indice de l'opération doit s'exécuter en O(log n) temps (en supposant que les binaires de recherche) et, si elle n'est pas triée, l'indice va s'exécuter en O(n) fois.
    • Si a1 est triée et vous fournir une méthode de l'indice qui tire parti de ce fait pour revenir à l'index par la recherche binaire plutôt que d'itération, alors l'indice de l'opération doit s'exécuter en O(log n) temps vs O(n) fois. Ce qui est incorrect?
    • Cette méthode est très rapide aussi, mais à l'aide de hachages, c'est comme voyager plus vite que la vitesse de la lumière. J'ai couru un test avec les deux méthodes pour 10 000 numéros (juste pour le plaisir de l'expérimentation). Votre méthode a eu 1.3 secondes sur un avg mais avec des hachages il a pris de 0,009 secondes sur avg..
    • -1 pour cette méthode. Par Exemple: x - Tableau de 1000 éléments, non triées x2 - Tableau des mêmes éléments, triés Benchmark.bm { |t| t.report('test1') { x.index_by { |c| c }.values_at(*x2).compact } t.report('test2') { x.sort_by { |v| x2.index v } } } test1 réel: 0.000709 test2 réel: 0.048563
    • Celui-ci fait l'affaire pour moi. Dans mon cas, la commande de tableau est plus petit que celui d'être commandé, je n'ai donc: a2.sort_by{|x| a1.index(x.id) || a1.taille } pour le reste des éléments à conserver leur commande. Merci pour votre réponse, l'homme!
    • La solution donnée est O(n^2), même si a1 est triée en raison de Tableau#index ne pas faire une recherche binaire. Ruby 2.3 ajouté bsearch_index donc si vous passez à cela, l'indice lui-même est en O(logn). Compte tenu de ce qui est fait n fois pour a2, il sera en O(nlogn). @isqad la solution est préférable. Mais il crée des 3 objets. 1. index_by de hachage, 2. values_at tableau 3. compact un autre tableau. Vous pouvez simplifier en utilisant compact!. C'est donc l'espace-temps de la complexité à ce point.

    InformationsquelleAutor pguardiario
  3. 17

    J'aime la accepté de répondre, mais dans ActiveSupport il est index_by qui fait de la création de la première hachage encore plus facile. Voir Façon la plus propre de créer un Hachage à partir d'un Tableau

    En fait, vous pourriez le faire en une seule ligne depuis Énumérable prend en charge index_by ainsi:

    a2.index_by(&:id).values_at(*a1)
    • Cela ne fonctionne que si vous n'avez pas de doublons dans votre liste d'origine. Index par va remplacer les id en double. Cela peut ou peut ne pas être un problème pour vous.
    InformationsquelleAutor Eric Woodruff
  4. 7

    Inspiré par Eric Woodruff Répondre, je suis venu avec la suite de la vanille Ruby solution:

    a2.group_by(&:object_id).values_at(*a1).flatten(1)

    Documentation de la méthode:

    • J'aime cette solution meilleure. C'est efficace (et je soupçonne plus efficace que @pguardiario de la solution) et, surtout, permet à deux éléments de a2 avoir la même valeur de "id". La question n'est pas que les id sont uniques, encore de réponses à certaines questions, y compris celle qui est sélectionnée, dépendent de l'id est unique.
    InformationsquelleAutor Ajedi32