Skip List

Una skip list és una estructura de dades probabilística a base de llistes encadenades paral·leles.

Descripció

Una skip list pretén ser una millora d'una llista encadenada ordenada. Conté una jerarquia de subllistes encadenades, cadascuna d'elles sent un subconjunt de la següent i amb la darrera sent un conjunt amb tots els elements. Els elements van sent afegits de forma aleatòria, de manera que la cerca arreu de la llista podria saltar (skip, en anglès) nombroses capes.

La skip list queda organitzada en capes (les subllistes). La capa de més avall és simplement una llista encadenada estàndard. Cada capa superior i+1 és una via ràpida per recórrer les capes inferiors. Un element present a la capa i té una probabilitat fixa p de formar part de la capa immediatament superior (i+1). De mitjana, cada element apareix a 1/(1-p) llistes i l'element més alt (sovint un element fantasma més petit que tots els altres) apareix a O(log1/p n) capes. 

1
1-----4---6
1---3-4---6-----9
1-2-3-4-5-6-7-8-9-10

Consulta

La consulta d'un element comença pel més petit, a la capa més alta. Per cada capa visitada, recorrem els elements fins a topar amb un element superior (o el final de la capa) o un element igual al que cerquem. En el primer cas, davallem verticalment (des del darrer element inferior que hem trobat, que sempre trobarem a sota) a la capa immediata. L'esperança del nombre de passos per cada capa és 1/p. El cost total de la consulta és O(log1/p (n/p)); que esdevé O(log (n)) si hom considera p com fixa. Conforme juguem amb el valor d'aquest paràmetre p, obtenim un compromís entre temps de recerca i espai de memòria consumit.

Altres operacions

La inserció i la supressió s'implementen com una llista encadenada, excepte que els elements alts han de ser inserits i suprimits a múltiples capes.

Rendiment

Degut a la seva naturalesa probabilística, aquestes estructures de dades no ofereixen les mateixes garanties, al pitjor cas, que un arbre binari balancejat. En efecte, és poc probable però tanmateix possible que la distribució aleatòria produeixi una estructura molt desequilibrada.

De fet, aquestes llistes funcionen molt bé, a la pràctica, i tenen la fama de ser més fàcilment implementables que llurs equivalent deterministes a base de balanceig d'arbres.

Dintre de les implementacions reals, hom ha mesurat que llurs rendiments en temps i en espai són millors que els dels Arbre-B. Això és degut a factors com ara la proximitat de les dades des la memòria cau.

Història

Les skip lists van ser inventades per William Pugh l'any 1990.[1]

Referències

  1. ↑ «Skip lists: a probabilistic alternative to balanced trees» (en anglès). Communications of the ACM, 6-1990.

Read other articles:

Free TV Networks

American digital multicasting and FAST network media company Free TV NetworksTrade nameFree TV NetworksCompany typeJoint ventureIndustryMediaPredecessorCircle (broadcast operations)[1]FoundedNovember 7, 2023 (2023-11-07)FounderJonathan KatzHeadquartersAtlanta, Georgia, United StatesKey peopleJonathan Katz (President/CEO)David Decker (President, Content Sales, Warner Bros. Discovery)Jim Packer (President of Worldwide Television Distribution, Lionsgate)Pat LaPlatney (Pres...

 

Farida Jalal

Farida JalalFarida JalalLahir14 Maret 1949 (umur 75)New Delhi, IndiaKebangsaanIndiaPekerjaanAktris, komedianTahun aktif1967 - sekarangSuami/istri Tabrez Barmavar ​ ​(m. 1978; meninggal 2003)​ PenghargaanAktris Pendukung Terbaik: Paras (1972) Aktris Pendukung Terbaik: Henna (1992) Aktris Terbaik (Kritikus): Mammo (1995) Aktris Pendukung Terbaik: Dilwale Dulhania Le Jayenge (1996) Farida Jalal (lahir 14 Maret 1949) adalah seorang aktris...

 

Subacute sclerosing panencephalitis

Medical conditionSubacute sclerosing panencephalitisOther namesDawson diseaseSubacute sclerosing panencephalitis.SpecialtyNeurology, Infectious DiseaseSymptomsBehavior changes, seizures, spasticity, poor coordination, comaUsual onset6-15 years after infection with measlesCausesMeasles virusRisk factorsMeasles infectionDiagnostic methodEEG, Serologic testing, brain biopsyPreventionMeasles vaccineTreatmentSupportive treatmentMedicationIntrathecal interferon alpha, intravenous ribavirin, isoprin...

Order of the Throne

Order of the Throne Order of the Throne, granted by Hassan II of MoroccoAwarded by The King of MoroccoTypeorderEstablished16 May 1963CountryMoroccoStatusactiveFounderHassan II of MoroccoRibbon of the order The Order of the Throne (Arabic: وسام العرش, romanized: Wissam al-Arch) is a state decoration of the Kingdom of Morocco awarded for distinguished services of a civil or military nature. The Order was instituted on 16 May 1963 by King Hassan II of Morocco, who reigned between 1...

 

République populaire d'Angola

République populaire d'AngolaRepública Popular de Angola 1975–1992Drapeau Armoiries Hymne Angola Avante Informations générales Statut République marxiste-léniniste État communiste à parti unique Capitale Luanda Langue(s) Portugais Religion Athéisme d'État, catholicisme Monnaie Kwanza Histoire et événements 11 novembre 1975 Indépendance de la république populaire d'Angola 1975-1991 Guerre civile 23 mars 1991 Révision constitutionnelle, abandon du parti unique 31 mai 1991 Sign...

 

Liga II

Disambiguazione – Divizia B rimanda qui. Se stai cercando altre competizioni rumene o moldave, vedi Divizia B (disambigua). Liga IISport Calcio TipoSquadre di club FederazioneFRF Paese Romania OrganizzatoreFederaţia Română de Fotbal Cadenzaannuale Aperturaagosto Chiusuramaggio Partecipanti20 squadre Formulagirone all'italiana+play-off Promozione inSuperLiga Retrocessione inLiga III Sito Internethttp://www.liga2.ro StoriaFondazione1934 Numero edizioni86 Detentore FC Pol...

Big Brother (Australian TV series) season 5

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Big Brother (Australian TV series) season 5 – news · newspapers · books · scholar · JSTOR (May 2020) (Learn how and when to remove this template message) Season of television series Big BrotherSeason 5Presented byGretel KilleenNo. of days100No. of housemates20...

 

Template talk:Desserts

Food and drink: Desserts Template‑class Food portalThis template is within the scope of WikiProject Food and drink, a collaborative effort to improve the coverage of food and drink related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Food and drinkWikipedia:WikiProject Food and drinkTemplate:WikiProject Food and drinkFood and drink articlesTemplateThis template does not require a rating...

 

Motorsports Hall of Fame of America

Hall of fame for American motorsports personalities 29°11′8″N 81°4′10″W / 29.18556°N 81.06944°W / 29.18556; -81.06944 The Motorsports Hall of Fame of America (MSHFA) is hall of fame that honors motorsports competitors and contributors from the United States from all disciplines, with categories for Open Wheel, Stock Cars, Powerboats, Drag Racing, Motorcycles, Sports Cars, Aviation, At Large, Off-Road and Historic. Periodic recognition is given to specialty ...

Newsweek

Weekly magazine based in New York City For the 1978–1989 Australia North Queensland current affairs television program, see Newsweek (TV program). NewsweekCover of the September 5, 1983, issueEditor-in-chiefNancy Cooper[1]Former editorsMalcolm Muir (1937–1959)Osborn Elliott (1961–1976)[2]Jon Meacham (2006–2010)[3]CategoriesMagazine, publisherPublisherDev Pragad [4][5], President and CEOTotal circulation(2015)100,000[6]First issueFebruary...

 

Saint-Paul Asylum, Saint-Rémy (Van Gogh series)

Series of paintings by Vincent van Gogh Hospital at Saint-Rémy-de -ProvenceArtistVincent van GoghYear1889MediumOil on canvasDimensions58 cm × 45 cm (23 in × 18 in)LocationMusée d'Orsay, Paris Saint-Paul Asylum, Saint-Rémy is a collection of paintings that Vincent van Gogh made when he was a self-admitted patient at the Saint-Paul asylum in Saint-Rémy-de-Provence, since renamed the Clinique Van Gogh, from May 1889 until May 1890. During much of h...

 

The Oxfordshire Museum

The Oxfordshire MuseumThe entrance to the museumShown within OxfordshireLocationFletcher's House, Park Street, Woodstock, Oxfordshire, EnglandCoordinates51°50′54″N 1°21′26″W / 51.8483°N 1.3572°W / 51.8483; -1.3572Websitewww.oxfordshire.gov.uk/the_oxfordshire_museum The Oxfordshire Museum (also known as Oxfordshire County Museum) is in Woodstock, Oxfordshire, England, located in Fletcher's House, Park Street, opposite the Bear Hotel.[1] It is a regi...

Saint-Aubin-du-Cormier

Saint-Aubin-du-Cormiercomune Saint-Aubin-du-Cormier – Veduta LocalizzazioneStato Francia Regione Bretagna Dipartimento Ille-et-Vilaine ArrondissementFougères CantoneFougères-1 TerritorioCoordinate48°16′N 1°24′W / 48.266667°N 1.4°W48.266667; -1.4 (Saint-Aubin-du-Cormier)Coordinate: 48°16′N 1°24′W / 48.266667°N 1.4°W48.266667; -1.4 (Saint-Aubin-du-Cormier) Superficie27,57 km² Abitanti3 756[1] (2009) Densit�...

 

Echinococcosis

Parasitic disease of tapeworms of the Echinococcus type This article is about the disease. For the organism, see Echinococcus. Medical conditionEchinococcosisOther namesHydatid disease, hydatidosis, echinococcal disease, hydatid cystEchinococcus granulosa life cycle (click to enlarge)SpecialtyInfectious diseaseSymptomsVariable[1]CausesTapeworm of the Echinococcus type[1]Diagnostic methodMedical imaging, blood tests[1]PreventionVaccination of sheep, treating infected do...

 

Proofs of trigonometric identities

Collection of proofs of equations involving trigonometric functions There are several equivalent ways for defining trigonometric functions, and the proofs of the trigonometric identities between them depend on the chosen definition. The oldest and most elementary definitions are based on the geometry of right triangles. The proofs given in this article use these definitions, and thus apply to non-negative angles not greater than a right angle. For greater and negative angles, see Trigonometri...

GENESIS (software)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: GENESIS software – news · newspapers · books · scholar · JSTOR (November 2016) (Learn how and when to remove this message) Original author(s)Dr. James M. BowerInitial release1988Stable release2.4[1] / November 2014; 9 years ago...

 

العلاقات الغانية الغينية

العلاقات الغانية الغينية غانا غينيا   غانا   غينيا تعديل مصدري - تعديل   العلاقات الغانية الغينية هي العلاقات الثنائية التي تجمع بين غانا وغينيا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة غانا غينيا المساح�...

 

UTC+05:45

UTC+05:45Zona waktuPeta dunia dengan zona waktu berwarnaPerbedaan UTCUTCUTC+05:45Waktu kini05:07, 19 June 2024 UTC+05:45 [refresh]Meridian utama86,25 derajat TKelompok tanggal-waktu UTC+05:45: Biru (Desember), Jingga (Juni), Kuning (sepanjang tahun), Biru Muda - Daerah laut UTC+05:45 merupakan perbedaan waktu dari UTC dari +05:45. Waktu ini digunakan di Nepal. Sebagai waktu standar (sepanjang tahun) Asia Selatan Nepal - Waktu Nepal sejak tahun 1986 Ini adalah perkiraan dari waktu rata-rata Ka...

Gaualofa

Polynesian voyaging canoe The Gaualofa History Samoa NameGaualofa OwnerSamoa Voyaging Society BuilderSalthouse Boatbuilders Launched2009 Identification MMSI number: 518387000 Callsign: 5WGK StatusActive General characteristics Class and typeVaka Moana Tonnage13 tonnes[1] Length72 ft (22 m) overall[1] Beam21 ft (6.4 m)[1] Draft6 ft (1.8 m)[1] PropulsionSail / PV electric Sail plancrabclaw sails Complement14-16[1] Gaualofa is...

 

Soulseek

Peer-to-peer (P2P) filesharing network SoulseekScreenshot of the older Soulseek 157 NS 13e client version on Microsoft WindowsDeveloper(s)Nir ArbelInitial releaseApril 8, 2001; 23 years ago (2001-04-08)[1][2]Stable releaseSoulseekQt build 2024.02.01 (February 1, 2024; 6 months ago (2024-02-01)) [±]Preview releaseNone [±] Written inC++, QtOperating systemMicrosoft Windows, and macOS and Linux in the newest Qt client...