Nim и Go против Wikipedia


Прошлая неделя на Хабре прошла под знаком Go.
В последнее время я все чаще начал слышать о новом языке Nim.
Оба языка компилируемые, быстрые, кроссплатформенные и достаточно легкие для входа. Go уже успел завоевать любовь многих, Nim только начинает этот путь. Мне были интересны оба языка, но сложно выбрать кто из них окажется лучше пусть даже и для проектов for fun.
Лучше всего входить в новый язык используя его на практике. Писать стандартные бенчмарки — это скучно. Надо было придумать нечто вдохновляющее. И такая идея пришла. У всех был момент, когда заходишь на Википедию и переходишь по связанным ссылка из статьи в статью. Мне стало интересно сколько понятий отделяют одну статью от другой. Другими словами, через какое минимально количество ссылок надо пройти, что бы добрать от статьи А до статьи В.
Идея алгоритма тривиальная. Мы создаем очередь, в которую складываем все новый wiki-страницы, полученные в процессе парсинга текущей. И начина я с начальной wiki-странице мы ходим в цикле: взял первую страницу в очереди-скачал-распарсил-записал все вложенные ссылки в очередь-проверил условия выхода.

Для того, чтобы не ходить по циклическим ссылкам мы должны вести учет уже посещенных страниц. Еще нам нужно сохранять иерархические отношения «родитель-потомок», для того, чтобы в конце вывести всю цепочку страниц. Для этих задач нам подойдет простой словарь, где ключом будет текущая wiki-страница, а значением ее предок. Таким образом дойдя до финала поиска мы сможем по цепочке вернуться к коревой wiki-странице.


Решение на Go потребовало внешней библиотеки для парсинга HTML и в целом получилось несколько многословным из-за возврата статуса ошибок (но это скорее фишка языка).

Исходник на Go
package main

import (
        "flag"
        "fmt"
        "github.com/PuerkitoBio/goquery"
        "log"
        "net/url"
        "strings"
)

const stopTerm string = "#stop#"

var (
        lang      string
        printMode int
)

func findLinks(url string) []string {
        result := make([]string, 0)

        doc, err := goquery.NewDocument(fmt.Sprintf("https://%s.wikipedia.org%s", lang, url))
        if err != nil {
                log.Fatal(err)
        }

        doc.Find("a").Each(func(i int, s *goquery.Selection) {
                href, _ := s.Attr("href")
                if strings.HasPrefix(href, "/wiki/") && !strings.Contains(href, ":") && !strings.Contains(href, "#") {
                        result = append(result, href)
                }
        })

        return result
}

func printTerm(term string, mode int) {
        if printMode == mode {
                val, err := url.QueryUnescape(term)
                if err != nil {
                        log.Fatal(err)
                }
                fmt.Printf("%s\n", val)
        }
}

func printParent(term string, dict map[string]string) {
        val, _ := url.QueryUnescape(term)
        fmt.Printf("\n\n>> Found: %s\n", val)
        n := dict[term]
        for n != stopTerm {
                val, _ := url.QueryUnescape(n)
                fmt.Printf("parent: %s\n", val)
                n = dict[n]
        }
}

func searchPath(begin string, end string) {
        dict := make(map[string]string)
        dict[begin] = stopTerm

        queue := make(chan string, 10000000)
        queue <- begin

        for {
                currentNode := <-queue
                printTerm(currentNode, 1)
                for _, v := range findLinks(currentNode) {
                        if _, ok := dict[v]; !ok {
                                dict[v] = currentNode
                                if v == end {
                                        printParent(v, dict)
                                        return
                                }

                                queue <- v

                                printTerm(v, 0)
                        }
                }
        }
}

func main() {
        beginTerm := flag.String("b", "Sort", "Begin wiki term")
        endTerm := flag.String("e", "SAP", "Finish wiki term")
        langFlag := flag.String("l", "ru", ".wikipedia.org")
        printModeFlag := flag.Int("p", 0, "Print mode 0 - print all; 1- print current term; 2 - silent")
        flag.Parse()

        lang = *langFlag
        printMode = *printModeFlag

        searchPath("/wiki/"+url.QueryEscape(*beginTerm), "/wiki/"+url.QueryEscape(*endTerm))
}



Ссылка на репозиторий git: https://bitbucket.org/tonatoz/go_wiki_path
Решение на Nim обошлось использование стандартных библиотек, зато в количестве 9 штук.

Исходник на Nim
import httpclient, streams, htmlparser,
    xmltree, strtabs, strutils,
    queues, cgi, os

proc printTerm(term: string) = 
    echo decodeUrl(term)

proc findLinks(url: string) : seq[string] =
    result = @[]
    let html = getContent(r"https://ru.wikipedia.org" & url)
    for a in parseHtml(newStringStream(html)).findAll("a"):
        let href = a.attrs["href"]
        if href.startsWith("/wiki/") and not href.contains({':', '#'}):
            result.add(href)

proc printParent(term: string, dict: StringTableRef) =
    printTerm("\nFound! " & term)
    var n = dict[term]
    while n != "#stop#":
        printTerm("parent: " & n)
        n = dict[n]

proc searchPath(beginTerm: string, endTerm: string) = 
    var dict = newStringTable(modeCaseInsensitive)
    var queue = initQueue[string]()

    dict[beginTerm] = "#stop#"
    queue.add(beginTerm)

    while true:
        var currentNode = queue.dequeue  
        printTerm(currentNode)
        for a in findLinks(currentNode):
            if not dict.hasKey(a):
                dict[a] = currentNode
                if a == endTerm:
                    printParent(a, dict)
                    return
                queue.add(a)

let args = commandLineParams()
case args.len:
    of 2:
        searchPath("/wiki/" & encodeUrl(args[0]), "/wiki/" & encodeUrl(args[1]))
    of 0:
        searchPath("/wiki/Sort", "/wiki/SAP")
    else:   
        echo r"use >>program  "



Ссылка на репозиторий git: https://bitbucket.org/tonatoz/nim_wiki_path
В примере по умолчанию мы ищем пут от страницы Sort до страницы SAP: Sort ⇒ GNU/Linux ⇒ SAP

На Ubintu в vagrant получаются следующая картина:

Язык Размер исполняемого файла Скорость на стандартном примере Скорость на сложном примере UNIX ⇒ PostgreSQL
Go 5 959 424 byte real 0m6.031s
user 0m0.216s
sys 0m0.120s
real 0m26.078s
user 0m2.788s
sys 0m1.648s
Nim 701 589 byte real 0m1.974s
user 0m0.240s
sys 0m0.024s
real 1m2.921s
user 0m4.224s
sys 0m1.376s

Итоги неоднозначные. Nim генерирует файл гораздо меньшего объема и лучше справляется на простых примерах, Go вырывается в лидеры на более сложных цепочках. Понятно, что оба исходника надо тюнить для достижения идеала, но уже сейчас я смог понять для себя что Go крут, а у Nim явно большое будущее.

В заключение несколько получившихся цепочек:
Nim ⇒ Си_(язык_программирования) ⇒ Go
Windows ⇒ 1985_год ⇒ Индия
Интернет ⇒ Английский_язык ⇒ Новая_Зеландия ⇒ Кошка
Стрела ⇒ Бамбуковые ⇒ Велосипед ⇒ Коленный_сустав
Half-Life_2:_Episode_Three ⇒ Half-Life_(серия_игр) ⇒ Эмблема ⇒ Вечность
Go ⇒ 2009 ⇒ 9_марта ⇒ Счастье
Nim ⇒ 2015 ⇒ 9_марта ⇒ Счастье

© Habrahabr.ru