| dbpedia-owl:abstract
|
- Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O para la mayoría de las operaciones). Una lista por saltos se construye por capas. La capa del fondo (la más baja) es una sencilla lista enlazada. Cada capa subsiguiente es como una "vía rápida" para la lista de la capa bajo esta. Un elemento de la capa i aparece en la capa i+1 con una probabilidad fija p. En promedio, cada elemento aparece en 1/(1-p) listas, el elemento más alto (generalmente un elemento inicial colocado al principio de la lista por saltos) aparece en O(log n) listas. Para buscar un elemento se empieza con el elemento inicial de la lista de la capa más alta hasta alcanzar el máximo elemento que es menor o igual al buscado, se pasa a la capa siguiente (debajo de la actual) y se continua la búsqueda. Se puede verificar que el número esperado de pasos en cada lista enlazada es 1/p. De manera que el costo total de búsqueda es O(log n / p), que es lo mismo que O(log n) cuando p es una constante. Dependiendo del valor escogido para p, se puede favorecer el costo de búsqueda contra el costo de almacenamiento. Las operaciones de inserción y borrado se implantan como las de sus correspondientes listas enlazadas, salvo que los elementos de las capas superiores deben ser insertados o borrados de más de una lista enlazada. A diferencia de los árboles de búsqueda balanceados, el peor caso para las operaciones de listas por saltos no está garantizado como logarítmico, dado que es posible aunque poco probable, que se produzca una estructura no balanceada. Sin embargo, las listas por saltos trabajan bien en la práctica y el esquema de balanceo es más sencillo de implementar que el de los árboles binarios balanceados. Las listas por saltos son útiles también para cómputo paralelo, dado que se pueden realizar inserciones en paralelo sobre segmentos diferentes sin tener luego que balancear la estructura.
- File:Skip list. svg In informatica, una skip list è una struttura dati probabilistica per la memorizzazione di una lista ordinata di elementi. Essa utilizza una gerarchia di liste concatenate che connettono sottosequenze di elementi. Queste liste ausiliarie permettono di percorrere la lista con grande efficienza, paragonabile a quella di un albero di ricerca binario bilanciato. Il livello più basso rappresenta la lista concatenata.
- スキップリスト（skip list）は確率的アルゴリズムのためのデータ構造であり、並列な連結リストに基づいている。効率は平衡2分探索木と同等である。大半の操作について平均O(log n)である。 基本的にスキップリストは順序つきの連結リストの前向きのリンクを追加したものである。Pughによる原著論文によると、前向きのリンクはGeometric/Negative Binomial distributionという乱数を用いた手法で追加されていて、リスト上の探索においてリストの一部を高速に飛ばすことができる。挿入と探索と削除は対数の乱数時間で行われる。 1990年にWilliam Pughによって発明されたスキップリストは計算機科学における重要なアルゴリズムのうち最も年代の浅いものである。
- Lista z przeskokami (ang. skip list) – w informatyce struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL, czy czerwono-czarne. Została opracowana przez Williama Paugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi . W zwykłej liście każdy element posiada połączenie (ze względu na prostotę implementacji - najczęściej realizowane poprzez wskaźnik) wyłącznie do elementu następnego, w liście z przeskokami takich połączeń jest więcej - oprócz bezpośredniego następnika, wskazują także elementy znajdujące się dalej. Liczba połączeń powiązana z elementem określa jego stopień (ang. degree, lub wysokość), przy czym -te połączenie wskazuje na kolejny element stopnia co najmniej . Stopnie węzłów są wybierane losowo, ale z rozkładem geometrycznym (prawdopodobieństwa dane wzorem, gdzie); np. dla liczba elementów stopnia 1 powinna stanowić 50% całości, stopnia 2 - 25%, stopnia 3 - 12% itd. Dzięki temu rozwiązaniu można szybciej przechodzić całą listę, a ponadto dzięki informacji o jej uporządkowaniu pomijać ("przeskakiwać") nieistotne fragmenty listy.
- SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária para a maioria das operações. Basicamente, uma skip list é um aglomerado de listas encadeadas com ligações adicionais, adicionadas de modo aleatório de acordo com a distribuição Geométrica/Negativa Binomial, os quais permitem evitar a busca em parte da lista, 'pulando' alguns valores. Inserção, busca e remoção são operadas em tempo logarítmico. Descoberta em 1989 por William Pugh, a Skiplist é uma das mais recentes dentre aquelas estruturas de dados mais importantes da Ciência da computação.
- A skip list is a data structure for storing a sorted list of items, using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n). Each link of the sparser lists skips over many items of the full list in one step, hence the structure's name. These forward links may be added in a randomized way with a geometric / negative binomial distribution. Insert, search and delete operations are performed in logarithmic expected time. The links may also be added in a non-probabilistic way so as to guarantee amortized (rather than merely expected) logarithmic cost.
- File:Skip list. svg 跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。 基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。
- Список с пропусками — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O среднее время для большинства операций). В основе списка с пропусками расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением, таким образом, чтобы поиск по списку мог быстро пропускать части этого списка. Вставка, поиск и удаление выполняются за логарифмическое случайное время.
- En skipplista är en länkad lista där vissa element har pekare som går flera steg framåt (framåtpekare). En vanlig konfiguration är att låta antalet steg framåt vara en tvåpotens, som nedan en sådan skipplista kallas för en perfekt balanserad skipplista. Notera att listan utnyttjar sina pekare optimalt om antalet element är en tvåpotens. Noderna i listan kan kallas efter antalet framåtpekare de har. Noden med värde 2 har i detta fall 2 framåtpekare och kallas därför för en nivå-2-nod. När man stoppar in eller tar bort noder ur listan kommer listans balans att ändras (t. ex. kommer inte var fjärde nod längre att ha en framåtpekare som pekar 4 steg framåt). Det skulle såklart gå att ordna om listan för att få den perfekt balanserad men detta är inte praktiskt användbart. Istället är det vanligt att man nöjer sig med en mindre strikt balans som bygger på sannolikhet. Eftersom en perfekt balanserad skipplista innehåller 50% nivå nivå-1-noder, 25% nivå-2-noder, osv. så kan detta användas för att slumpa antalet framåtpekare i en nyinstoppad nod. I en sådan här sannolikhetsbalanserad skipplista pekar en nods i:te pekare på nästa nod som är en nivå-i-nod eller högre, dvs. inte nödvändigtvis på den nod som är steg framåt. Listans nivå är lika med antalet pekare i header-noden. I exemplet ovan är listans nivå 4.
- Une Skip-list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en O(log n) avec une grande probabilité.
|
| rdfs:comment
|
- File:Skip list. svg In informatica, una skip list è una struttura dati probabilistica per la memorizzazione di una lista ordinata di elementi. Essa utilizza una gerarchia di liste concatenate che connettono sottosequenze di elementi. Queste liste ausiliarie permettono di percorrere la lista con grande efficienza, paragonabile a quella di un albero di ricerca binario bilanciato. Il livello più basso rappresenta la lista concatenata.
- スキップリスト（skip list）は確率的アルゴリズムのためのデータ構造であり、並列な連結リストに基づいている。効率は平衡2分探索木と同等である。大半の操作について平均O(log n)である。 基本的にスキップリストは順序つきの連結リストの前向きのリンクを追加したものである。Pughによる原著論文によると、前向きのリンクはGeometric/Negative Binomial distributionという乱数を用いた手法で追加されていて、リスト上の探索においてリストの一部を高速に飛ばすことができる。挿入と探索と削除は対数の乱数時間で行われる。 1990年にWilliam Pughによって発明されたスキップリストは計算機科学における重要なアルゴリズムのうち最も年代の浅いものである。
- File:Skip list. svg 跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。 基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。
- Una skip list o lista por saltos es una Estructura de datos, basada en Listas enlazadas paralelas con eficiencia comparable a la de un árbol binario (tiempo en orden O para la mayoría de las operaciones). Una lista por saltos se construye por capas. La capa del fondo (la más baja) es una sencilla lista enlazada. Cada capa subsiguiente es como una "vía rápida" para la lista de la capa bajo esta. Un elemento de la capa i aparece en la capa i+1 con una probabilidad fija p.
- SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária para a maioria das operações. Basicamente, uma skip list é um aglomerado de listas encadeadas com ligações adicionais, adicionadas de modo aleatório de acordo com a distribuição Geométrica/Negativa Binomial, os quais permitem evitar a busca em parte da lista, 'pulando' alguns valores. Inserção, busca e remoção são operadas em tempo logarítmico.
- Lista z przeskokami (ang. skip list) – w informatyce struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL, czy czerwono-czarne. Została opracowana przez Williama Paugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi .
- Список с пропусками — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O среднее время для большинства операций). В основе списка с пропусками расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением, таким образом, чтобы поиск по списку мог быстро пропускать части этого списка.
- En skipplista är en länkad lista där vissa element har pekare som går flera steg framåt (framåtpekare). En vanlig konfiguration är att låta antalet steg framåt vara en tvåpotens, som nedan en sådan skipplista kallas för en perfekt balanserad skipplista. Notera att listan utnyttjar sina pekare optimalt om antalet element är en tvåpotens. Noderna i listan kan kallas efter antalet framåtpekare de har. Noden med värde 2 har i detta fall 2 framåtpekare och kallas därför för en nivå-2-nod.
- A skip list is a data structure for storing a sorted list of items, using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n). Each link of the sparser lists skips over many items of the full list in one step, hence the structure's name.
- Une Skip-list (liste à enjambements) est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en O(log n) avec une grande probabilité.
|
