Co jest trudniejsze: tasowanie posortowanej talii lub sortowanie potasowanej talii?

Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy i i zwraca prawdziwy iff ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania: $n$ $a$ $b$ $a < b$

Tablica jest obecnie posortowana. Twórz jednolicie (lub w przybliżeniu jednakowo) losowo wybraną permutację.
Tablica składa się z pewnej permutacji wybieranej z natury jednolicie losowo. Utwórz posortowaną tablicę.

Moje pytanie brzmi

Które zadanie wymaga więcej energii asymptotycznie?

Nie jestem w stanie precyzyjniej zdefiniować pytania, ponieważ nie wiem wystarczająco dużo o związku między teorią informacji, termodynamiką lub czymkolwiek innym, co jest potrzebne, aby odpowiedzieć na to pytanie. Sądzę jednak, że pytanie można precyzyjnie zdefiniować (i mam nadzieję, że ktoś mi w tym pomoże!).

Teraz, algorytmicznie, moja intuicja jest taka, że są one równe. Zauważ, że każdy rodzaj jest tasowaniem w odwrotnym kierunku i na odwrót. Sortowanie wymaga porównania, podczas tasowania, ponieważ wybiera losową permutację z wybory, wymaga przypadkowych bitów. Wymaga to zarówno tasowania, jak i sortowania $\log n! \approx n \log n$ $n!$ $\log n! \approx n \log n$ zamiany. $n$

Wydaje mi się jednak, że odpowiedź powinna być zgodna z zasadą Landauera , która mówi, że potrzeba trochę energii, aby „trochę wymazać”. Intuicyjnie myślę, że oznacza to, że sortowanie tablicy jest trudniejsze, ponieważ wymaga „skasowania” bitów informacji, przechodząc od niskoenergetycznego stanu o wysokim entropii do zaburzenia o wysokim uporządkowaniu. Ale z drugiej strony, dla każdego obliczenia, sortowanie przekształca tylko jedną permutację w drugą. Ponieważ jestem tutaj kompletnym nie-ekspertem, miałem nadzieję, że ktoś ze znajomością związku z fizyką może pomóc „rozwiązać” ten problem! $n \log n$

(Pytanie nie otrzymało żadnych odpowiedzi na stronie matematyka.se , więc zamieszczam je tutaj ponownie. Mam nadzieję, że jest ok.)

algorithms algorithm-analysis information-theory permutations entropy usul
źródło

I haven't thought this through at all, so caveat lector. If we start with a sorted array, then use merge sort, but instead of comparing, we use the random bits to do the merging (so instead of returning true iff

a < b

$a<b$ we return true iff the random bit is

1

$1$ ). The base case where we have two arrays of size one produces the two possible arrays of size two with a uniform probability. I haven't gotten any further than that.

Luke Mathieson

I think that in order to answer this question, you first need to define the relative costs of operation; how much does it cost to read data, write data, and generate/obtain a random number?

mitchus

@mitchus: I am mainly curious about the physical limits if we assume "optimally efficient" computers. My rough understanding is that there is a physical lower bound on the amount of energy required to "erase" a bit of information, while other operations require much less energy. So I wonder if this intuition is correct and formalizable enough to yield an answer.

usul

What do you mean by erasing a bit? Overwriting it? As far as I know computers don't usually erase anything (except for privacy reasons) but merely "forget" about it by de-allocating the associated memory region. But maybe I am not grasping the abstraction level correctly here :)

mitchus

@Patrick87 Unfortunately, a uniform energy model is too far from the truth to use it; see Evaluating Algorithms according to their Energy Consumption by Fudeus née Bayer and Nebel (2009).

Raphael

Odpowiedzi:

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small.

Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.

Peter Shor
źródło

Thanks very much! Can I ask a possibly naive follow up? Suppose I change the wording of the question so that the sorting algorithm is given some fixed permutation of the items and must sort them. Now, if you subscribe to a Bayesian philosophy and have a uniform belief on this input, it seems the answer should be the same. But under a philosophy that there is no randomness in the input (although I don't know what it is), the argument seems to fail. How do I resolve the paradox? Thanks again!!

usul

@usul: in that case,you've still erased the bits, so the algorithm still takes

(n \ln n) k T

$(n \ln n) kT$ energy. It's just that in this case, there is a better algorithm you could have used, if you had known which fixed permutation the input was.

Peter Shor

Neither. Any circuit can be made reversible by keeping track of the input, and the energy dissipation of reversible computation can be made arbitrarily small.

rphv
źródło

but making it reversible might make it non-efficient. What is the relation between the optimal algorithms. BTW, i don't think they compare. Shuffling inherently requires randomness (and any different randomness will produce a different output). Sorting may be deterministic. "Reversing" sorting will shuffle in a deterministic way.

Ran G.

By "efficient" do you mean time, space, or some combination of the two? Making a computation reversible doesn't necessarily add asymptotic time complexity, and there exist reversible versions of every computation that use no more space than the original [Vitányi05].

rphv

As long as you keep the input around, any circuit can be made reversible. If you don't want to keep information that can reconstruct the original permutation around, the sorting circuit cannot be made reversible.

Peter Shor