Tõhusad strateegiad sokkide sidumiseks pesuhunnikust

Optimaalsete sokkide sidumismeetodite leidmine

Eile puhtast pesust sokke sidudes mõistsin, et minu meetod on ebaefektiivne. Kasutasin naiivset otsingut, valisin ühe soki ja kordasin hunnikut, et leida sellele sobiv, mis nõuab keskmiselt üle n²/8 soki itereerimist. See tekitas mõtte: kas arvutiteadlasena võiks sellele ülesandele paremini läheneda?

Meelde tuli sorteerimine suuruse või värvi järgi, et saavutada O(NlogN) lahendus. Mitte-kohalike lahenduste, nagu räsimine, kasutamine ei ole aga teostatav, kuna ma ei saa oma sokke paljundada. Kui võtta arvesse n paari sokipaari (2n elementi), kus igal sokil on täpselt üks sobiv paar, siis milline on kõige tõhusam viis nende sidumiseks, kasutades kuni logaritmilist lisaruumi? Siin on minu eesmärk uurida üldist teoreetilist lahendust ja kaaluda praktilisi aspekte, sealhulgas väiksemat, eristatavat sokkide arvu minu ja mu abikaasa vahel.

Täiustatud tehnikad tõhusaks sokkide sidumiseks

Esimeses skriptis kasutame sokkide sidumiseks sorteerimist. Kasutades sorted() funktsiooni, paneme sokid järjekorda. Seejärel kordame sorteeritud loendit, võrreldes külgnevaid elemente. Kui need ühtivad, ühendame need ja liigume järgmise paari juurde. See lähenemisviis suurendab selle tõhusust sorted() funktsioon, mis töötab O(NlogN) ajas. Kasutamine append() funktsioon lisab sobitatud paarid tulemuste loendisse, tagades, et kogume kõik paarid tõhusalt.

Teine skript kasutab sidumiseks räsikaarti. Initsialiseerime tühja sõnaraamatu, sock_mapja tühi nimekiri, pairs. Sokke läbides kontrollime, kas iga sokk on juba sõnastikus. Kui on, ühendame selle sõnaraamatu sokiga kasutades pop(), mis eemaldab soki sõnastikust. Kui sokki sõnastikus pole, lisame selle väärtuseks soki endaga. See meetod tagab, et iga sokk paaritatakse kohe pärast selle sobivuse leidmist, mille tulemuseks on O(N) aja keerukuslahendus.

Jaga ja valluta, et saavutada tõhus sokkide sidumine

Kolmas skript kasutab jaga ja valluta strateegiat. Jagame sokkide loendi rekursiivselt väiksemateks alamloenditeks, kuni iga alamloend sisaldab ainult ühte või kahte sokki. Põhijuht kontrollib, kas alamloendi pikkus on väiksem kui kaks, tagastades tühja loendi. Kui pikkus on kaks, tagastab see paari, kui sokid sobivad. Keskpunkt, mid = len(socks) // 2, kasutatakse loendi poolitamiseks. Vasak- ja parempoolseid alamloendeid töödeldakse ja liidetakse rekursiivselt. Ühendamisel võrreldakse vasakpoolsest ja paremast alamloendist pärit sokke ja paaristatakse, kui need vastavad. The while loop tagab paaride tõhusa liitmise.

Kõik need meetodid pakuvad erineva lähenemisviisi sokkide sidumise probleemi lahendamisele, tasakaalustades aja ja ruumi keerukuse vahel. Sorteerimismeetod on lihtne, kuid kasutab sorteerimisalgoritmide võimsust. Hashmapi meetod on tõhus lineaarse aja keerukusega, kuid kasutab sõnastiku jaoks lisaruumi. Jaga ja valluta lähenemisviis on keerulisem, kuid pakub struktureeritud viisi probleemi rekursiivseks käsitlemiseks. Nendest tehnikatest aru saades ja neid rakendades saate tõhusalt siduda sokke suurest hunnikust, tagades optimaalse jõudluse.

def pair_socks(socks):
    sorted_socks = sorted(socks)
    pairs = []
    i = 0
    while i < len(sorted_socks) - 1:
        if sorted_socks[i] == sorted_socks[i + 1]:
            pairs.append((sorted_socks[i], sorted_socks[i + 1]))
            i += 2
        else:
            i += 1
    return pairs
socks = [1, 3, 2, 1, 2, 3]
print(pair_socks(socks))

def pair_socks(socks):
    sock_map = {}
    pairs = []
    for sock in socks:
        if sock in sock_map:
            pairs.append((sock, sock_map.pop(sock)))
        else:
            sock_map[sock] = sock
    return pairs
socks = [1, 3, 2, 1, 2, 3]
print(pair_socks(socks))

def pair_socks(socks):
    if len(socks) < 2:
        return []
    if len(socks) == 2:
        return [(socks[0], socks[1])] if socks[0] == socks[1] else []
    mid = len(socks) // 2
    left = pair_socks(socks[:mid])
    right = pair_socks(socks[mid:])
    pairs = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i][0] == right[j][0]:
            pairs.append((left[i][0], right[j][0]))
            i += 1
            j += 1
        elif left[i][0] < right[j][0]:
            i += 1
        else:
            j += 1
    return pairs + left + right
socks = [1, 3, 2, 1, 2, 3]
print(pair_socks(socks))

Alternatiivsete sokkide sidumisalgoritmide uurimine

Teine tõhus meetod sokkide sidumiseks hõlmab kahe osuti tehnikat. See meetod on eriti kasulik, kui sokid on juba sorteeritud või neid saab sorteerida ühe atribuudi, näiteks värvi või suuruse alusel. Kasutades kahte osutit, millest üks algab sorteeritud loendi algusest ja teine ​​lõpus, saame sokid kiiresti tuvastada ja siduda. Kahe osuti tehnika minimeerib vajalike võrdluste arvu, toimides lineaarses ajas O(N) pärast esialgset sortimist. See lähenemisviis on tõhus ja hõlpsasti rakendatav, muutes selle igapäevaseks kasutamiseks praktiliseks.

Praktikas võib sokkide esmane sorteerimine oluliselt vähendada probleemi keerukust. Näiteks kui sorteerime sokid värvi järgi, saame sokkide paaristamiseks kasutada ühte käiku, võrreldes külgnevaid elemente. Selline sorteerimise ja kahe osuti tehnika kombinatsioon tagab, et saame tõhusalt hakkama suure hulga sokkidega, isegi kui peame eristama eri tüüpi, näiteks erinevatele pereliikmetele kuuluvaid. See hübriidmeetod kasutab mõlema algoritmi tugevaid külgi, pakkudes tugeva lahenduse sokkide sidumise probleemile.