J'ai un tableau de hachage arbitraire, avec un élément du hachage un entier (appelez-le 'id'). Je veux trier ces hachages dans un nombre de compartiments (constant sur le tableau), où chaque segment est une plage arbitraire de 'ids' (par exemple 1-10, 15-20, 20-30). Quelle est la meilleure stratégie de tri pour cela? Est-il possible de se passer d'une boucle imbriquée?Quel est le moyen le plus efficace de trier une collection d'articles dans des seaux?
Si le nombre de compartiments est petit, vous êtes probablement mieux avec les boucles imbriquées. La boucle extérieure sur les hachages, et l'intérieur sur les seaux. O(n*m).
Si le nombre de hash, et le nombre de seaux sont grandes, vous pouvez:
hashes = sort(hashes)
buckets = sort(buckets) # sort by lower-bound of bucket
i = 0
foreach (hash in hashes) {
while (buckets[i].lower_bound > hash) {
i = i + 1
}
bucket[i].add(hash)
}
Les boucles essentiellement à travers les hash en les ajoutant au seau en cours et avancer au prochain seau au besoin. O (n * log (n) + m * log (m))
Si les hachages sont de bonne qualité, ils présenteront une distribution uniforme, de sorte que vous pouvez utiliser des godets répartis uniformément pour répartir la collection en un seul passage. .
Si vous souhaitez également que les hachages soient triés dans les compartiments, utilisez un algorithme de tri normal une fois que tout est dans des compartiments. Ce serait une utilisation inhabituelle des hachages, cependant. (Si vous n'essayez pas de trier dans des compartiments, le mot «trier» est un terme impropre.) Ce que vous vouliez vraiment, c'était le partitionnement.)
Vous ne parlez pas de langue/plate-forme, mais pour des raisons d'efficacité. touches (C#):
var histogram = new[] { 0, 10, 15, 20, 30, 40 };
var values = new[] { 12, 14, 5, 6, 7, 1, 34, 26, 17 };
var bars = values.GroupBy(v => histogram.First(b => v < b));