Как да внедрите динамично програмиране в Swift

В нашето проучване на алгоритмите сме приложили много техники за получаване на резултати. Някои концепции са използвали специфични за iOS модели, докато други са по-обобщени. Въпреки че не е изрично споменато, някои от нашите решения са използвали определен стил на програмиране, наречен динамично програмиране. Макар и пряко на теория, приложението му понякога може да бъде нюансирано. Когато се прилага правилно, динамичното програмиране може да има мощен ефект върху начина, по който да пишете код. В това есе ще представим концепцията и прилагането на динамичното програмиране.

Запази за по късно

Ако сте закупили нещо чрез Amazon.com, ще бъдете запознати с термина на сайта - „Запиши за по-късно“. Както фразата предполага, купувачите имат възможност да добавят артикули в кошницата си или да ги запишат в „Списък с желания“ за по-късен преглед. Когато пишем алгоритми, често се сблъскваме с подобен избор на изпълняващи действия (извършване на изчисления), тъй като данните се интерпретират или съхраняват резултатите за по-късна употреба. Примерите включват извличане на JSON данни от RESTful услуга или използване на Core Data Framework:

В iOS, дизайнерските модели могат да ни помогнат за времето и да координираме как се обработват данните. Специфичните техники включват операции с много нишки (например Grand Central Dispatch), известия и делегиране. Динамичното програмиране (DP), от друга страна, не е непременно една техника на кодиране, а по-скоро как да мислим за действия (например подпроблеми), които се случват при функциониране на функция. Полученото решение за DP може да се различава в зависимост от проблема. В най-простата си форма динамичното програмиране разчита на съхранение на данни и повторна употреба, за да увеличи ефективността на алгоритъма. Процесът на повторна употреба на данни също се нарича мемоизация и може да приеме много форми. Както ще видим, този стил на програмиране осигурява множество предимства.

Фибоначи отново

В есето за рекурсия сравнихме изграждането на класическата последователност на стойностите на масива, използвайки както итеративни, така и рекурсивни техники. Както беше обсъдено, тези алгоритми са проектирани да произвеждат последователност от масив, а не за изчисляване на конкретен резултат. Като вземем това предвид, можем да създадем нова версия на Фибоначи, за да върнем единична Int стойност:

func fibRecursive (n: Int) -> Int {
    ако n == 0 {
        върнете 0
    }
    
    ако n <= 2 {
        връщане 1
    }
    
    връщане fibRecursive (n: n-1) + fibRecursive (n: n-2)
}

На пръв поглед изглежда, че тази на пръв поглед малка функция също би била ефективна. Въпреки това, при по-нататъшен анализ виждаме множество рекурсивни повиквания, за да може да се изчисли какъвто и да е резултат. Както е показано по-долу, тъй като fibRecursive не може да съхранява предварително изчислени стойности, неговите рекурсивни повиквания се увеличават експоненциално:

Фибоначи запомнени

Нека опитаме различна техника. Замислен като вложена функция Swift, fibMemoized улавя връщащата стойност на масива от нейната подфункция fibSequence, за да изчисли крайната стойност:

разширение Int {
    
    // запомнена версия
    мутиращ func fibMemoized () -> Int {
        
        // изгражда последователност на масив
        func fibSequence (_ последователност: Array  = [0, 1]) -> Array  {
            
            var final = масив  ()
            
            // мутирано копие
            var изход = последователност
            
            нека i: Int = output.count
            
            // задайте основно условие - линейно време O (n)
            ако i == аз {
                връщане на изхода
            }
            
            нека резултатите: Int = изход [i - 1] + изход [i - 2]
            output.append (резултати)
            
            // задайте итерация
            final = fibSequence (изход)
            връщане окончателно
            
        }
        
        
        // изчисляване на краен продукт - постоянно време O (1)
        нека резултатите = fibSequence ()
        нека отговори: Int = резултати [results.endIndex - 1] + резултати [results.endIndex - 2]
        отговор на връщане
        
    }
}

Въпреки че fibSquence включва рекурсивна последователност, основният му случай се определя от броя на заявените позиции на масива (n). По отношение на производителността, ние казваме, че fibSequence работи в линейно време или O (n). Това подобрение на производителността се постига чрез запаметяване на последователността Array, необходима за изчисляване на крайния продукт. В резултат на това всяка пермутация на последователност се изчислява веднъж. Ползата от тази техника се вижда при сравняване на двата алгоритъма, показани по-долу:

Най-къси пътища

Запомнянето на кодове също може да подобри ефективността на програмата до степен да направи на пръв поглед трудни или почти нерешими въпроси. Пример за това може да се види с алгоритъма на Дижкстра и най-късите пътища. За да прегледаме, създадохме уникална структура от данни, наречена Path, с цел запаметяване на специфични обходни метаданни:

// класът на пътя поддържа обекти, които съдържат "границата"
клас път {
    
    вар общо: Int
    вар дестинация: Vertex
    var предишен: Path?
   // инициализация на обект
    в него(){
        дестинация = Vertex ()
        общо = 0
    }
}

Това, което прави Path полезен, е неговата способност да съхранява данни в предишни посетени възли. Подобно на нашия преработен алгоритъм на Фибоначи, Path съхранява кумулативния ръб на тежестта на всички пресечени върхове (общо), както и пълна история на всеки посетен Vertex. Използвано ефективно, това позволява на програмиста да отговаря на въпроси като сложността на навигацията до определена дестинация Vertex, ако обиколката наистина е била успешна (при намирането на дестинацията), както и списъка на посещаваните възли. В зависимост от размера и сложността на графиката, липсата на тази информация може да означава, че алгоритъмът отнема толкова време, за да (пре) изчисли данните, че става твърде бавен, за да бъде ефективен, или да не може да реши жизненоважни въпроси поради недостатъчни данни.

Хареса ли ви това есе? Прочетете и открийте другото ми съдържание в Medium или получете пълната книга във формат EPUB, PDF или Kindle.