Вступление
Прошла неделя на Хабре прошла под знаком Go.
В последнее время я все чаще начал слышать о новом языке Nim.
Оба языка компилируемые, быстрые, кроссплатформенные и достаточно легкие для входа. Go уже успел завоевать любовь многих, Nim только начинает этот путь. Мне были интересны оба языка, но сложно выбрать кто из них окажется лучше пусть даже и для проектов for fun.
Идея
Лучше всего входить в новый язык используя его на практике. Писать стандартные бенчмарки — это скучно. Надо было придумать нечто вдохновляющее. И такая идея пришла. У всех был момент, когда заходишь на Википедию и переходишь по связанным ссылка из статьи в статью. Мне стало интересно сколько понятий отделяют одну статью от другой. Другими словами, через какое минимально количество ссылок надо пройти, что бы добрать от статьи А до статьи В.
Алгоритм
Идея алгоритма тривиальная. Мы создаем очередь, в которую складываем все новый wiki-страницы, полученные в процессе парсинга текущей. И начина я с начальной wiki-странице мы ходим в цикле: взял первую страницу в очереди-скачал-распарсил-записал все вложенные ссылки в очередь-проверил условия выхода.
Для того, чтобы не ходить по циклическим ссылкам мы должны вести учет уже посещенных страниц. Еще нам нужно сохранять иерархические отношения «родитель-потомок», для того, чтобы в конце вывести всю цепочку страниц. Для этих задач нам подойдет простой словарь, где ключом будет текущая wiki-страница, а значением ее предок. Таким образом дойдя до финала поиска мы сможем по цепочке вернуться к коревой wiki-странице.
Go
Решение на Go потребовало внешней библиотеки для парсинга HTML и в целом получилось несколько многословным из-за возврата статуса ошибок (но это скорее фишка языка).
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", "<your_lang>.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
Решение на Nim обошлось использование стандартных библиотек, зато в количестве 9 штук.
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 <begin term> <end term>"
Ссылка на репозиторий 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_марта ⇒ Счастье
ссылка на оригинал статьи http://habrahabr.ru/post/260883/
Добавить комментарий