Nim і Go проти Wikipedia

Вступ
Минулий тиждень на Хабре пройшла під знаком Go.
Останнім часом я все частіше почав чути про новий мовою Nim.
Обидві мови компилируемые, швидкі, кросплатформені і досить легкі для входу. Go вже встиг завоювати любов багатьох, Nim тільки починає цей шлях. Мені були цікаві обидві мови, але складно вибрати хто з них виявиться краще нехай навіть і для проектів for fun.

Ідея
Найкраще входити в новий мову використовуючи його на практиці. Писати стандартні бенчмарки — це нудно. Треба було придумати щось надихаюче. І така ідея прийшла. У всіх був момент, коли заходиш на Вікіпедію і переходиш по пов'язаним посилання зі статті в статтю. Мені стало цікаво скільки понять відокремлюють одну статтю від іншої. Іншими словами, через яке мінімально кількість посилань треба пройти, щоб добратися від статті до статті Ст.

Алгоритм
Ідея алгоритму тривіальна. Ми створюємо чергу, в яку складаємо все новий wiki-сторінки, отримані в процесі парсинга поточної. І починаючи з початкової wiki-сторінці ми ходимо в циклі: взяв першу сторінку в черзі-скачав-распарсил-записав всі вкладені посилання в чергу-перевірив умови виходу.

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

Go
Рішення на 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(int i, 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, int mode) {
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]; !ок {
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("е", "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 штук.

Исходник на 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 <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_марта ⇒ Щастя

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.