Han's

Quelqu'un connaît-il les algorithmes , espace linéaire, algorithmes de tri des nombres de Yijie Han ? Ce résultat apparaît dans un article assez court ( Tri déterministe en temps linéaire et en espace . J. Alg. 50: 96-105, 2004) qui regroupe essentiellement de nombreux résultats antérieurs, avec des adaptations. Mon problème est que c'est écrit d'une manière plutôt vague, sans entrer dans les détails. Il s’appuie largement sur des documents antérieurs, notamment un autre de Han ( Amélioration du tri des entiers rapides dans l’espace linéaire). $O(n \log\log n)$ $O(n \log\log n)$ . Information and Computation 170 (1): 81–94) écrit dans le même style. J'ai beaucoup de difficulté à comprendre ces deux documents, en particulier la manière dont ils adaptent et utilisent les résultats précédents. J'apprécierais toute aide.

Ceci est bien sûr trop large et vague pour être considéré comme une question appropriée, mais j'espère développer une discussion à travers plusieurs questions et réponses bien définies.

Pour commencer, voici ma première question précise. Dans la lemme 2 de l'info. Comp. papier, il existe un algorithme récursif de temps permettant de trouver le plus petit nombre entier dans un ensemble de petits nombres entiers emballés chacun dans des mots RAM. La description de l'algorithme ne mentionne pas comment le cas de base est traité. Dans ce cas, il est nécessaire de faire la sélection en temps . Comment cela peut-il être fait? $O(n/k \log k)$ $n$ $k$ $k=O(n)$ $O(\log k)$

ds.algorithms sorting Ari
la source

Il serait parfaitement approprié de lui écrire: [email protected].

Joseph O'Rourke

Oui. Nous avons déjà discuté de cette question générale, et la bonne façon de résoudre ce problème consiste à envoyer un courrier électronique à l'auteur.

Suresh Venkat

Cela inclut une question spécifique sur un article datant de 7 ans et ayant déjà passé le processus d’évaluation par les pairs. Bien que Ari puisse envoyer un courrier électronique à l'auteur, cela semble être une question idéale pour ce site. Je ne comprends pas la déviation.

Huck Bennett,

Bien sûr, la première chose que j'ai faite a été d'écrire Han. Pas de réponse. Ensuite, j'ai contacté quelqu'un qui avait fait des recherches sur le tri des nombres entiers. Il a dit qu'après avoir pris connaissance des faits, il avait trouvé les documents trop compliqués pour mériter un investissement supplémentaire de son temps. C'est quand je suis venu ici. Si quelqu'un connaît Han et peut attirer son attention sur moi, ce serait très bien aussi.

Ari

Le tri général n'a pas de borne inférieure à

. Bien au contraire - c'est un tri limité aux comparaisons qui a cette limite. Le problème ici ne consiste pas à limiter les entrées, mais à améliorer le modèle de calcul. Mon modèle de calcul est l’une des variantes de la RAM au coût unitaire, et j’autorise toutes les hypothèses raisonnables (telles que la disponibilité des constantes dépendant de la longueur du mot).

Ω (n \log n)

$\Omega(n\log n)$

Ari

Réponses:

Je me demandais juste la même chose.

Heureusement, j'ai pu trouver un article de journal publié en 2011 qui explique tout cela; De plus, vous n'avez pas besoin d'un abonnement pour le visualiser: Analyse d'implémentation et de performance du tri d'arbres exponentiel

Je recommande de lire l'intégralité de l'article pour apprendre comment le mettre en œuvre et mieux comprendre la théorie sous-jacente. Il montre également comment les arbres exponentiels se comparent aux arbres à tri rapide et aux arbres binaires. Voici l'extrait pertinent lié à Han le temps, l' espace linéaire, entier algorithme de tri $\bf O(n \log\log n)$ :

Yijie Han a donné une idée qui réduit la complexité au temps attendu dans un espace linéaire. [6] La technique qu'il utilise est la transmission coordonnée des nombres entiers sur l'arbre de recherche exponentielle d'Andersson [8] et la division multiple temporelle linéaire des bits des nombres entiers. Au lieu d'insérer un entier à la fois dans l'arbre de recherche exponentiel, il a transmis tous les entiers un niveau de l'arbre de recherche exponentiel à la fois. Ce transfert coordonné offre la possibilité d'effectuer une division multiple dans le temps linéaire et donc d'accélérer l'algorithme. Cette idée peut permettre d'accélérer les choses, mais dans la pratique, il est très difficile de gérer les entiers par lots.

[6] Y. Han, Tri déterministe en temps linéaire et en espace linéaire O (n log log n), 34e STOC, 2002.

[8] A. Andersson, Tri rapide déterministe et recherche dans l'espace linéaire, Symposium IEEE sur les fondements de l'informatique, 1996.

À
la source

Pourquoi le vote négatif?

Suresh Venkat

Je viens d'ajouter ce lien vers la page wikipedia de l' arborescence Exponential . FYI: Cet article pourrait être publié après que la question a été posée.

@AT, pourriez-vous développer votre réponse et expliquer comment elle répond à la question. Pour le moment, la seule chose qu'il donne est un lien vers un article dans un journal.

Kaveh

Eh bien, j'ai déjà abandonné le papier de Han, alors je suis heureux que vous ayez pu fournir cette aide. Je ne m'attendais pas vraiment à voir quoi que ce soit à mon retour ici aujourd'hui. Merci! Je vais lire ce nouveau document et voir si cela m'aide à progresser sur le document de Han.

Ari

Eh bien, je viens de le lire, et je vais admettre que j’ai peut-être complètement mal compris, mais à part cela, il semble y avoir un léger problème. Les auteurs prétendent que leur arbre a la hauteur O

, mais si l’arbre a la hauteur

, alors il l’a

feuilles, et donc moins de

nœuds au total. Supposons généreusement que chaque nœud contient

clés. Ensuite , l'arbre contient moins de

(\log \log n)

$(\log\log n)$

h

$h$

(h + 1)!

$(h+1)!$

2 \cdot (h + 1)!

$2\cdot(h+1)!$

h + 2

$h+2$

clés. Si

alors

. Quoi qu’il en soit, même si les auteurs sont corrects, ils ne réalisent ni letriO

, ni expliquent Han, ce qui n’a donc aucune utilité.

2 \cdot (h + 2)!

$2\cdot(h+2)!$

2 \cdot (h + 2)! = n

$2\cdot(h+2)!=n$

h = Ω (\log n / \log \log n)

$h=\Omega(\log n/\log\log n)$

(\log \log n)

$(\log\log n)$

Ari

Je ne suis pas sûr de la réponse (je ne suis pas passé par le papier) mais je pense que cela devrait aider. Les nombres sont regroupés dans un seul mot, de sorte que les opérations sur un seul mot prennent un temps O (1). S'il y a, par exemple, k nombres de h bits, la taille des mots dépend de k, h, qui dépend également de la plage de nombres. Nous utilisons donc des techniques de réduction de plage qui peuvent réduire la plage de nombres de manière à ce que plusieurs nombres puissent tenir dans un seul mot. Ensuite, en créant les masques de bits appropriés, nous pouvons trouver des entiers plus grands distincts des plus courts en considérant deux mots à la fois. Cela peut être fait en un temps O (1). (Ontuition: pour cela, chaque numéro stocké dans word est associé à un bit de drapeau, puis nous soustrayons deux mots ... si le bit de drapeau disparaît, son nombre est plus petit).

De même, en utilisant ce qui précède, nous pouvons également trier tout mot contenant k nombres en temps O (log k) (tri bitonique).

Édition: Algorithme pour trier 2k nombres compris entre 0 et m-1 dans un mot où chaque nombre prend la taille L de = log (m + k) +2.

$K_1$

$K_2$

Répétez l'opération pour t = log k à 0.

Partie 1 - séparez le mot original Z en deux mots A et B.

$K_2$ $K_1$
$2^t L$
B = Z- (Z & M).

Partie 2

$K_1$ $K_1$
M = M- (M décalé à gauche L-1 places).
MIN = (B & M) OU (A- (A & M))
MAX = (A & M) OU (B- (B & M))
$2^t L$
Pour finir, ORing MAX et MIN nous renvoyons Z.

J'ai donné le croquis, j'espère que vous pourrez remplir les détails nécessaires requis.

Singhsumit
la source

Je ne comprends pas bien ce que vous suggérez. L'hypothèse est que les entiers sont déjà petits et que k d'entre eux sont déjà regroupés dans un seul mot. Proposez-vous de réduire davantage leur taille? Si oui, que faites-vous alors? De plus, je sais comment trier une séquence bitonique condensée en un seul mot en temps O (log k), ou trier une séquence générale (non bitonique) en temps O (log ^ 2 k). Si vous connaissez un algorithme qui trie une séquence générale en temps O (log k), pourriez-vous s'il vous plaît le décrire plus en détail? (Un tel algorithme résoudrait bien sûr le problème de sélection.)

Ari,

Je ne suis pas en train de réduire davantage la taille, je vous ai suggéré comment réduire la taille qui n’était pas requise dans votre réponse. Désolé pour la confusion.

Singhsumit

Sauf erreur, cela ressemble à l'algorithme de tri des séquences bitoniques. Il ne trie pas les séquences générales. Par exemple, trie-t-il la séquence 3,0,2,0, où le 3 est dans le champ le plus à gauche (le plus significatif)?

Ari

3 0 2 0 est séparé n nous obtenons A = 3 2 et B = 0 0 puis MAX devient 3 2 et MIN est 0 0. Nous avons alors un nouveau Z égal à 3 2 0 0. Toute séquence générale a une séquence bitonique de taille 2. à chaque itération, ces tailles sont doublées et enfin, en log k fois, nous avons notre réponse.

Singhsumit

Non, les chiffres ne sont pas compactés, mais seulement décalés. Dans la première itération, nous divisons des paires de nombres différant par le bit fort de leur position, ce qui donne A = 0 3 0 2 et B = 0 0 0 0, donc MIN = 0 0 0 0, MAX = 0 3 0 2 et Z = 3 0 2 0. Dans la deuxième itération, nous divisons des paires différant par le bit bas de leur position. Nous obtenons donc à nouveau A = 0 3 0 2, B = 0 0 0 0, et encore Z reste inchangé.

Ari