X + Y sortering

Olöst problem inom datavetenskap :

Finns det en $X+Y$ sorteringsalgoritm snabbare än $O(n^{2}\log n)$ ?

(fler olösta problem inom datavetenskap)

Geometrisk visualisering av sorteringsproblemet ${\displaystyle X+Y} .$ Ingångsmängderna $X$ och $Y$ representeras av uppsättningarna av vertikala och horisontella svarta linjer (respektive), och målet med problemet är att sortera korsningspunkterna efter positionerna för den röda diagonalen linjer genom dem.

Inom datavetenskap är sortering med ${\boldsymbol {X}}+{\boldsymbol {Y}}$ problemet med att sortera talpar efter deras summor . Tillämpningar av problemet inkluderar minimering av transitpriser , VLSI -design och gles polynommultiplikation. Liksom med jämförelsesortering och heltalssortering mer generellt, kan algoritmer för detta problem endast baseras på jämförelser av dessa summor, eller på andra operationer som endast fungerar när indata är små heltal.

Det är okänt om detta problem har en jämförelsebaserad lösning vars körtid är asymptotiskt snabbare än att sortera en ostrukturerad lista med lika många objekt. Därför har forskningen kring problemet fokuserat på två tillvägagångssätt för att lösa frågan om en sådan förbättring är möjlig: utvecklingen av algoritmer som förbättrar ostrukturerad sortering i deras antal jämförelser snarare än i deras totala körtid, och nedre gränser för antal jämförelser baserat på räkning av celler i underavdelningar av högdimensionella utrymmen. Båda tillvägagångssätten är historiskt knutna samman, eftersom de första algoritmerna som använde få jämförelser var baserade på svagheten i de cellräknande nedre gränserna.

Problembeskrivning och historik

Indata till sorteringsproblemet ${\displaystyle X+Y} består av två ändliga$ samlingar av nummer $X$ och ${\displaystyle Y} ,$ av samma längd. Problemets utdata är samlingen av alla par av ett tal från $X$ och ett tal från ${\displaystyle Y} ,$ ordnade i sorterad ordning efter summan av varje par. Som ett litet exempel, för ingångarna $X=\{1,2,9\}$ och $Y=\{0, 4,9\}$ , bör utgången vara listan med par

$$(1,0),\,(2,0),\,(1,4),\,(2,4),\,(9,0),\,(1,9),\ ,(2,9),\,(9,4),\,(9,9)$$

av ett element från $X$ och ett element från ${\displaystyle Y} ,$ listade i sorterad ordning efter deras summor av par

$$1,2,5,6,9,10,11,13,18.$$

Ett sätt att lösa problemet skulle vara att konstruera paren som ska sorteras (den kartesiska produkten av de två samlingarna) och använda dessa par som indata till en standardjämförelse- sorteringsalgoritm som merge sort eller heapsort . När ingångarna har längden $n$ bildar de $n^{2}$ par, och tiden för att sortera paren på detta sätt är $O (n^{2}\log n)$ . När det gäller dess stora O-notation är denna metod den snabbaste kända algoritmen för $X+Y$ -sortering. Huruvida det finns en snabbare algoritm är ett öppet problem , ställd av Elwyn Berlekamp före 1975.

En variant av problemet sorterar summamängden , uppsättningen av summor av par, med dubblettsummor kondenserade till ett enda värde . För denna variant kan storleken på summamängden vara betydligt mindre än $n^{2}$ och utdatakänsliga algoritmer för att konstruera den har undersökts.

Ansökningar

Steven Skiena berättar om en praktisk tillämpning vid minimering av transitpriser , ett exempel på problemet med den kortaste vägen : hitta den billigaste flygbiljetten med två hopp mellan två givna städer, från en indata som beskriver både kostnaden för varje hopp och vilka hopppar som kan vara kombineras till en enda biljett. Skienas lösning består av att sortera humlepar efter deras totala kostnad som en instans av sorteringsproblemet ${\displaystyle X+Y} och sedan testa de resulterande paren i denna sorterade ordning tills man hittar en som är tillåten.$ För att generera de sorterade paren i denna ordning använder Skiena en prioriterad kö av par, som initialt bara innehåller ett enda par, det som består av de två billigaste humlen. Sedan, när ett par $(x,y)$ tas bort från kön och visar sig vara otillåtet, läggs ytterligare två par till, med ett av dessa två par som kombinerar $x$ med nästa hopp efter $y$ i en sorterad lista över hopp till destinationen, och det andra paret som kombinerar $y$ med nästa hopp efter $x$ i en sorterad lista med hopp från starten. På så sätt kan varje efterföljande par hittas i logaritmisk tid, och endast paren fram till det första tillåtna behöver sorteras.

$X+Y$ -sortering är den dyraste subrutinen i en algoritm för ett problem i VLSI -design, där man måste placera två underenheter av en VLSI-krets sida vid sida längs en kommunikationskanal för att minimera bredden på kanalen som behövs för att dra par av ledningar från en underenhet till den andra. Eftersom en underenhet kontinuerligt förskjuts i förhållande till den andra, ändras kanalbredden endast vid diskreta positioner där ändarna av två ledningar är i linje med varandra, och hitta den sorterade ordningen för dessa positioner för att beräkna sekvensen av ändringar av bredden kan utföras genom $X+Y$ sortering. Om detta sorteringsproblem kunde påskyndas, skulle det också påskynda denna VLSI-designuppgift.

En annan tillämpning involverar polynommultiplikation för polynom av en enda variabel som kan ha många färre termer än deras grader . Produkten av två polynom kan uttryckas som en summa av produkter av termpar, ett från varje polynom, och att placera dessa term-för-term-produkter i gradordning innebär att sortera dem efter summan av grader. Till exempel, instansen av $X+Y$ sortering med $n=3$ som ges som ett exempel ovan motsvarar multiplikationen av två tretermpolynom för att producera ett niotermspolynom :

$${\begin{aligned}(&x+x^{2}+x^{9})(1+x^{4}+x^{9})\\&=x+x^{2} +x^{5}+x^{6}+x^{9}+x^{10}+x^{11}+x^{13}+x^{18}.\\\end{aligned} }$$

Graderna är alltid heltal, så heltalsbaserade algoritmer för $X+Y$ -sortering kan användas. Men för polynom vars antal termer är jämförbara med deras grad, FFT-baserade polynommultiplikationsalgoritmer vara betydligt effektivare än term-för-term multiplikation.

Antal beställningar

En välkänd nedre gräns för ostrukturerad sortering, i beslutsträdsmodellen , är baserad på det faktoriella antalet sorterade order som en ostrukturerad lista kan ha. Eftersom varje jämförelse i bästa fall kan minska antalet möjliga beställningar med en faktor två, kräver sortering ett antal jämförelser som är minst lika med den binära logaritmen för faktorialen, som är $n\log _{2}nO(n)$ . Tidigt arbete med $X+Y$ -sortering följde ett liknande tillvägagångssätt genom att fråga hur många olika sorterade ordningar som är möjliga för detta problem, och bevisa att detta nummer är högst $O( n^{8n})$ . Men eftersom dess binära logaritm är högst ${\displaystyle 8n\log _{2}n+O(1)} ,$ mycket mindre än de kända tidsgränserna för ${ \displaystyle X+Y}$ sortering, denna metod kan bara leda till svaga nedre gränser för antalet jämförelser.

Beviset för denna gräns relaterar $X+Y$ -sortering till komplexiteten hos ett arrangemang av hyperplan i högdimensionell geometri. De två indatasamlingarna för sorteringsproblemet ${\displaystyle X+Y} består av$$2n$ -tal, som alternativt kan tolkas som de kartesiska koordinaterna för en punkt i $2n$ - dimensionellt utrymme $\mathbb {R} ^{2n}$ . Detta utrymme kan delas in i celler, så att inom en enda cell alla punkter motsvarar indata som producerar samma sorterade ordning. För denna underindelning ligger varje gräns mellan två celler inom ett hyperplan definierat av en likhet av par $x_{i}+y_{j}=x_{k}+y_{ \ell }$ , där $(x_{i},y_{j})$ och $(x_{k},y_{\ell } )$ är två par vars ordning ändras från en intilliggande cell till den andra. Dessa hyperplan genereras antingen av två disjunkta par, eller så har de de förenklade formerna $x_{i}=x_{k}$ eller $y_{j}=y_{ \ell }$ , så antalet distinkta hyperplan som kan bestämmas på detta sätt är

$$k=2{\binom {n}{2}}^{2}+2{\binom {n}{2}}.$$

Antalet celler som detta antal hyperplan kan dela ett utrymme med dimensionen $2n$ i är

$${\binom {k}{2n}}+{\binom {k}{2n-1}}+\cdots +{\binom {k}{0}}=O(n^{8n}).$$

har mängden $X+Y$$O(n^{8n})$ olika möjliga sorteringsordningar.

En liknande analysstil har varit mer framgångsrik när det gäller att utesluta snabba lösningar på vissa generaliseringar av $X+Y$ -sortering, genom att visa att de har för många beställningar att sortera snabbt. I synnerhet har Harper et al. (1975) $X$ och $Y$ separat och sedan konstruerar en tvådimensionell matris av värdena för $X+Y$ som sorteras både efter rader och efter kolumner innan du använder denna delvis sorterade data för att slutföra typen av $X+Y$ . Denna idé att använda en radsorterad och kolumnsorterad matris ligger till grund för metoden som Skiena använder i transportapplikationen och den kan minska antalet jämförelser med en konstant faktor i förhållande till naiv jämförelsesortering. Men för matriser vars rader och kolumner är sorterade på detta sätt är antalet möjliga sorterade ordningsföljder av hela matrisen mycket större än ${\displaystyle O(n^{8n})} ,$ så stort att alla jämförelsesorteringsalgoritmer som kan fungera för godtyckliga $n\ gånger n}$$) {\displaystyle \Omega (n^{2}\ log n)}$ matriser som är sorterade efter rader och kolumner kräver fortfarande jämförelser. Därför, om $X+Y$ -sorteringsproblemet ska lösas snabbt, måste lösningen använda ytterligare information om uppsättningen $X+Y$ utöver denna matrisordning.

Antal jämförelser

För det klassiska jämförelsesorteringsproblemet ligger tiden för att sortera och antalet jämförelser som behövs för att sortera inom konstanta faktorer av varandra. Men för $X+Y$ -sortering är antalet jämförelser mindre än den bästa kända tidsgränsen: Michael Fredman visade 1976 att $X+Y$ -sortering kan göras med endast $O(n^{2})$ jämförelser. Mer allmänt visade han att vilken uppsättning ${\displaystyle N} som helst$ , vars sorterade ordning redan har begränsats till en familj $\Gamma$ av beställningar, kan sorteras med hjälp av $\log _{2}|\Gamma |+O(N)$ jämförelser, genom en form av binär infogningssort . För sorteringsproblemet ${\displaystyle X+Y} ,$$N=n^{2}$ och $|\Gamma |=O(n^{8n})$ , så $\log _{2}|\Gamma |=O(n\log n)$ och Fredmans gräns innebär att endast $O(n^{2 })$ jämförelser behövs. I Fredmans metod kan dock tiden som behövs för att bestämma vilka jämförelser som ska utföras vara betydligt högre än gränsen för antalet jämförelser.

Den första explicita algoritmen som uppnår både ${\displaystyle O(n^{2})}-$ jämförelser och $O(n^{2}\log n)$ totalt komplexitet publicerades sexton år efter Fredman av Lambert (1992) . Algoritmen utför följande steg:

1. Sortera rekursivt de två uppsättningarna $X+X$ och $Y+Y$ .
2. Använd ekvivalensen $x_{i}-x_{j}\leq x_{k}-x_{\ell } \Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}$ för att härleda de sorterade ordningsföljderna av $XX$ och $YY$ utan ytterligare jämförelser .
3. Slå samman de två uppsättningarna $XX$ och $YY$ till en enda sorterad ordning, med hjälp av ett antal jämförelser linjära i deras totala storlek.
4. Använd den sammanslagna ordningen och ekvivalensen $x_{i}+y_{j}\leq x_{k}+y_ {\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}$ för att härleda den sorterade ordningen för $X+Y$ utan ytterligare jämförelser.

Den del av algoritmen som rekursivt sorterar $X+X$ (eller motsvarande $Y+Y$ ) gör det genom följande steg:

1. Dela upp $X$ i två lika stora underlistor $A$ och $B$ .
2. Sortera rekursivt $A+A$ och $B+B$
3. Härled ordningen på $A+B$ genom att endast använda jämförelser från ett enda sammanfogningssteg enligt ovan.
4. Slå samman de sorterade resultaten $A+A$ , $B+B$ och $A+B$ tillsammans.

Antalet jämförelser $C(n)$ som behövs för att utföra denna rekursiva algoritm på en ingång av $n$ objekt kan analyseras med hjälp av återfallsrelationen

$$C(n)\leq 2C(n/2)+O(n^{2}),$$

där $2C(n/2)$ termen för återkomsten räknar antalet jämförelser i de rekursiva anropen till algoritmen för att sortera $A+A$ och $B+B$ och termen $O(n^{2})$ räknar antalet jämförelser som används för att slå samman resultaten. Mastersatsen $C(n)=O(n^{2}).$ återfallsrelationer av denna form visar ) Den totala tidskomplexiteten är långsammare, $O(n^{2}\log n)$ , eftersom av stegen i algoritmen som använder redan gjorda jämförelser för att sluta sig till beställningar av andra uppsättningar. Dessa steg kan utföras i tiden $O(n^{2}\log n)$ genom att använda en standardjämförelse-sorteringsalgoritm med dess jämförelsesteg ersatta av de angivna slutledningarna.

Om endast jämförelser mellan element i $X+Y$ är tillåtna, så finns det också en matchande nedre gräns för $\Omega (n^{2})$ på antalet jämförelser, men med mer allmänna jämförelser som involverar linjära kombinationer av konstant antal element, behövs endast ${\displaystyle O(n\log ^{2}n)} jämförelser.$

Icke-jämförelsebaserade algoritmer

Precis som heltalssortering kan vara snabbare än jämförelsesortering för tillräckligt små heltal, gäller detsamma för $X+Y$ -sortering. I synnerhet, med heltalsinmatningar i intervallet från $0$ till någon övre gräns $M$ , kan problemet lösas i $O(n+M\ log M)$ operationer med hjälp av den snabba Fouriertransformen .

Relaterade problem

Flera andra problem inom beräkningsgeometri har likvärdig eller svårare komplexitet till $X+Y$ -sortering, inklusive att konstruera Minkowski-summor av trapppolygoner, hitta korsningspunkterna för ett arrangemang av linjer i sorterad ordning efter deras $x$ -koordinater, listar par av punkter i sorterad ordning efter deras avstånd, och testar om en rätlinjig polygon kan översättas för att passa in i en annan.

Problemet med att testa om två av paren i sorteringsproblemet ${\displaystyle X+Y} har lika stora summor kan lösas genom att sortera paren och sedan testa på varandra följande par för likhet.$ I sin tur kan den användas för att lösa 3SUM -problemet, vilket innebär att det är osannolikt att det har en starkt subkvadratisk algoritm.