This HTML5 document contains 142 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
n43https://github.com/flightaware/
n32http://videolectures.net/mit6046jf05_demaine_lec12/
dbpedia-svhttp://sv.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbrhttp://dbpedia.org/resource/
n7http://msdn.microsoft.com/en-us/library/
dbpedia-hehttp://he.dbpedia.org/resource/
n31http://ml.dbpedia.org/resource/
n38http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n14http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
n18http://www0.cs.ucl.ac.uk/staff/a.gonzalezbeltran/pubs/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
n37http://citeseerx.ist.psu.edu/viewdoc/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-thhttp://th.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
yago-reshttp://yago-knowledge.org/resource/
n36https://global.dbpedia.org/id/
n19https://parallelcomputing2017.wordpress.com/2017/04/17/skip-list/
n35https://github.com/m4nh/
n33https://xlinux.nist.gov/dads/HTML/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
n40http://opendatastructures.org/versions/edition-0.1e/ods-java/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Skip_list
rdf:type
yago:WikicatProbabilisticDataStructures yago:Cognition100023271 yago:Structure105726345 yago:Arrangement105726596 yago:PsychologicalFeature100023100 yago:WikicatDataStructures yago:DataStructure105728493 dbo:Building yago:Abstraction100002137
rdfs:label
Skip List Skiplist Skip list Skip list Skipplista Список с пропусками Skip-Liste Skip list Skip list Lista z przeskokami Список з пропусками スキップリスト 跳跃列表
rdfs:comment
スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária (ordem de O(log n)) 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. In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements В інформатиці, список з пропусками (англ. skip list) — структура даних, яка дозволяє швидкий пошук в упорядкованій послідовності елементів. Швидкий пошук стає можливим через утримання зв'язаної ієрархії підпослідовностей, кожна з яких пропускає кілька елементів з попереднього списку. Пошук стартує в найрозрідженішому списку, і триває допоки не знайдені два послідовних елементи один менший і один більший від шуканого елементу. Через ієрархічні зв'язки ці два елементи зв'язані з елементами наступного по щільності списку, в якому пошук продовжується. Таким чином ми доходимо до повного списку, без пропусків. Елементи пропущені у розріджених списках можуть обиратись імовірнісно. Список с пропусками (англ. Skip List) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций). В основе списка с пропусками лежит расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением, таким образом, чтобы поиск по списку мог быстро пропускать части этого списка. Вставка, поиск и удаление выполняются за логарифмическое случайное время. Lista z przeskokami (ang. skip list) – probabilistyczna 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 Pugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi 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. 在计算机科学中，跳跃列表是一种数据结构。它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是，优于数组的复杂度。 快速的查询效果是通过维护一个多层次的链表实现的，且与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少（见右下角示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择或确定性选择，其中前者更为常见。 En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements, ou liste à saut, est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en temps O(log n) avec une grande probabilité, où n est le nombre d'éléments contenus dans la liste. 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 <pre>|------------------------------>| ||-------------->|-------------->| ||------>|------>|------>|------>| ||-->|-->|-->|-->|-->|-->|-->|-->|-->|0 1 2 3 4 5 6 7 8 9</pre> 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. Listans nivå är lika med antalet pekare i header-noden. I exemplet ovan är listans nivå 4. 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(log n) para la mayoría de las operaciones). Una skip list és una estructura de dades probabilística a base de llistes encadenades paral·leles.
dbp:name
Skip list
foaf:depiction
n38:Skip_list.svg n38:Skip_list_add_element-en.gif
dcterms:subject
dbc:Probabilistic_data_structures dbc:Computer-related_introductions_in_1989 dbc:Linked_lists
dbo:wikiPageID
336155
dbo:wikiPageRevisionID
1121695506
dbo:wikiPageWikiLink
dbr:Pat_Morin dbr:MuQSS dbr:MemSQL dbr:Skip_graph dbr:Linked_list dbr:Scheduling_(computing) n14:Skip_list.svg n14:Skip_list_add_element-en.gif dbr:Random_access dbr:Adversary_(online_algorithm) dbr:Average-case_complexity dbr:William_Pugh_(computer_scientist) dbc:Computer-related_introductions_in_1989 dbr:Balanced_tree dbr:Apache_Portable_Runtime dbr:Array_data_structure dbr:C11_(C_standard_revision) dbc:Probabilistic_data_structures dbr:Computer_science dbr:MSDN dbr:Randomized_algorithm dbr:Cyrus_IMAP_server dbr:Lucene dbr:Ordered_sequence dbr:Moving_average dbc:Linked_lists dbr:Redis dbr:Non-blocking_algorithm dbr:Qt_(framework) dbr:Wireless_network dbr:Lock-free dbr:Apache_HBase dbr:Data_structure dbr:Priority_queue dbr:Parallel_computing dbr:Dictionary_of_Algorithms_and_Data_Structures dbr:Bloom_filter
dbo:wikiPageExternalLink
n7:ms379573(VS.80).aspx%23datastructures20_4_topic4 n18:AGB-comcom08.pdf n18:icc2007.pdf n19: n32: n33:skiplist.html n35:skimap_ros n37:summary%3Fdoi=10.1.1.47.514 n40:4_Skiplists.html n43:speedtables
owl:sameAs
dbpedia-sr:Скип_листа dbpedia-ca:Skip_List dbpedia-zh:跳跃列表 freebase:m.01xj5l dbpedia-sv:Skipplista wikidata:Q2005893 dbpedia-he:רשימת_דילוגים dbpedia-ru:Список_с_пропусками yago-res:Skip_list dbpedia-ja:スキップリスト dbpedia-fa:فهرست_پرشی n31:സ്കിപ്‌_ലിസ്റ്റ് dbpedia-fr:Skip_list n36:v1tA dbpedia-es:Skip_list dbpedia-pl:Lista_z_przeskokami dbpedia-de:Skip-Liste dbpedia-th:รายการข้าม dbpedia-pt:Skiplist dbpedia-it:Skip_list dbpedia-uk:Список_з_пропусками
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Infobox_data_structure dbt:Commons_category dbt:Citation_needed dbt:Blockquote dbt:Data_structures dbt:Reflist dbt:Probabilistic
dbo:thumbnail
n38:Skip_list.svg?width=300
dbo:wikiPageInterLanguageLink
dbpedia-de:Liste_(Datenstruktur)
dbp:author
William Pugh
dbp:source
Concurrent Maintenance of Skip Lists
dbp:text
Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.
dbp:type
List
dbo:abstract
In computer science, a skip list (or skiplist) is a probabilistic data structure that allows average complexity for search as well as average complexity for insertion within an ordered sequence of elements. Thus it can get the best features of a sorted array (for searching) while maintaining a linked list-like structure that allows insertion, which is not possible with a static array. Fast search is made possible by maintaining a linked hierarchy of subsequences, with each successive subsequence skipping over fewer elements than the previous one (see the picture below on the right). Searching starts in the sparsest subsequence until two consecutive elements have been found, one smaller and one larger than or equal to the element searched for. Via the linked hierarchy, these two elements link to elements of the next sparsest subsequence, where searching is continued until finally searching in the full sequence. The elements that are skipped over may be chosen probabilistically or deterministically, with the former being more common. Список с пропусками (англ. Skip List) — вероятностная структура данных, основанная на нескольких параллельных отсортированных связных списках с эффективностью, сравнимой с двоичным деревом (порядка O(log n) среднее время для большинства операций). В основе списка с пропусками лежит расширение отсортированного связного списка дополнительными связями, добавленными в случайных путях с геометрическим/негативным биномиальным распределением, таким образом, чтобы поиск по списку мог быстро пропускать части этого списка. Вставка, поиск и удаление выполняются за логарифмическое случайное время. Una skip list és una estructura de dades probabilística a base de llistes encadenades paral·leles. 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. En informatique, et plus précisément en algorithmique, une skip list, ou liste à enjambements, ou liste à saut, est une structure de données probabiliste, à base de listes chaînées parallèles. La plupart de ses opérations s'effectuent en temps O(log n) avec une grande probabilité, où n est le nombre d'éléments contenus dans la liste. スキップリスト（英: skip list）は、平衡二分探索木と似た用途に使う乱択アルゴリズムのデータ構造。連結リストを並列に連結させて作る。比較により順序づけ可能な要素を挿入し、スキップリスト内ではソートされた状態で保持される。ソートされた連想配列や集合の実装などに使える。挿入と探索と削除は平均O(log n)である。1989年にウィリアム・ピューが発表した。 スキップリストは順序つきの連結リストの前向きの飛び越しのリンクを追加したものである。ノードは幾何分布や負の二項分布にてランダムに高さを設定して追加され（高さ1が確率50%、高さ2が25%、高さ3が12.5%など）、リスト上の探索において連結リストの一部を高速に飛ばすことができる。 В інформатиці, список з пропусками (англ. skip list) — структура даних, яка дозволяє швидкий пошук в упорядкованій послідовності елементів. Швидкий пошук стає можливим через утримання зв'язаної ієрархії підпослідовностей, кожна з яких пропускає кілька елементів з попереднього списку. Пошук стартує в найрозрідженішому списку, і триває допоки не знайдені два послідовних елементи один менший і один більший від шуканого елементу. Через ієрархічні зв'язки ці два елементи зв'язані з елементами наступного по щільності списку, в якому пошук продовжується. Таким чином ми доходимо до повного списку, без пропусків. Елементи пропущені у розріджених списках можуть обиратись імовірнісно. 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(log n) para la mayoría de las operaciones). 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 <pre>|------------------------------>| ||-------------->|-------------->| ||------>|------>|------>|------>| ||-->|-->|-->|-->|-->|-->|-->|-->|-->|0 1 2 3 4 5 6 7 8 9</pre> 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 (till exempel 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. SkipList é uma estrutura de dados probabilística, baseada em listas ligadas paralelas, com eficiência comparável à de uma árvore binária (ordem de O(log n)) 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 , a Skiplist é uma das mais recentes dentre aquelas estruturas de dados mais importantes da Ciência da computação. 在计算机科学中，跳跃列表是一种数据结构。它使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是，优于数组的复杂度。 快速的查询效果是通过维护一个多层次的链表实现的，且与前一层（下面一层）链表元素的数量相比，每一层链表中的元素的数量更少（见右下角示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过的元素的方法可以是随机性选择或确定性选择，其中前者更为常见。 Lista z przeskokami (ang. skip list) – probabilistyczna 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 Pugha 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ść [height]), 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.
dbp:inventedBy
dbr:William_Pugh_(computer_scientist)
dbp:inventedYear
1989
gold:hypernym
dbr:Structure
prov:wasDerivedFrom
wikipedia-en:Skip_list?oldid=1121695506&ns=0
dbo:wikiPageLength
21409
foaf:isPrimaryTopicOf
wikipedia-en:Skip_list