Я изучал ответы, приведенные в Optimizing Haskell code, и заметил, что использование небольшого ввода действительно приведет к более быстрому выполнению Haskell по сравнению с Python.Производительность Haskell и изменчивых структур
Но поскольку набор данных вырос в размерах, Python взял на себя инициативу. Использование версии на основе hashmap улучшило производительность, но оно все еще отставало.
Хуже того, я пробовал транслитерировать словари Python в хеш-таблицы и наблюдал сильный удар производительности. Я действительно хочу понять, что происходит, поскольку для будущего приложения мне понадобятся измененные структуры.
Вот несколько измененный код Python:
#! /usr/bin/env python2.7
import random
import re
import cPickle
class Markov:
def __init__(self, filenames):
self.filenames = filenames
self.cache = self.train(self.readfiles())
picklefd = open("dump", "w")
cPickle.dump(self.cache, picklefd)
print "Built a db of length "+str(len(self.cache))
picklefd.close()
def train(self, text):
splitted = text.split(' ')
print "Total of %d splitted words" % (len(splitted))
cache = {}
for i in xrange(len(splitted)-2):
pair = (splitted[i], splitted[i+1])
followup = splitted[i+2]
if pair in cache:
if followup not in cache[pair]:
cache[pair][followup] = 1
else:
cache[pair][followup] += 1
else:
cache[pair] = {followup: 1}
return cache
def readfiles(self):
data = ""
for filename in self.filenames:
fd = open(filename)
data += fd.read()
fd.close()
return data
Markov(["76.txt"])
Хаскелл, с оригинальным ответом (train4), А HashMap его вариант (trainHM2) и Хеш транслитерации (trainHT):
{-# LANGUAGE BangPatterns,DeriveGeneriC#-}
import GHC.Generics (Generic)
import Data.List (foldl')
import Data.Hashable
import qualified Data.Map as M
import qualified Data.HashMap.Strict as HM
import qualified Data.ByteString.Char8 as B
import qualified Data.HashTable.IO as HT
--Using this instead of tuples yielded a 5~10% speedup
data StringTuple = STP !B.ByteString !B.ByteString deriving(Ord,Eq,Generic)
instance Hashable StringTuple
type Database3 = M.Map StringTuple (M.Map B.ByteString Int)
type DatabaseHM = HM.HashMap StringTuple (HM.HashMap B.ByteString Int)
type DatabaseHT = HT.BasicHashTable StringTuple DatabaseInnerHT
type DatabaseInnerHT = (HT.BasicHashTable B.ByteString Int)
train4 :: [B.ByteString] -> Database3
train4 words = foldl' update M.empty (zip3 words (drop 1 words) (drop 2 words))
where update m (x,y,z) = M.insertWith' (inc z) (STP x y) (M.singleton z 1) m
inc k _ = M.insertWith' (+) k 1
trainHM2 :: [B.ByteString] -> DatabaseHM
trainHM2 words = trainHM2G words HM.empty
where
trainHM2G (x:y:[]) !hm = hm
trainHM2G (x:y:z:rem) !hm = trainHM2G (y:z:rem) (HM.insertWith (inc z) (STP x y) (HM.singleton z 1) hm)
where inc k _ = HM.insertWith (+) k 1
trainHT :: [B.ByteString] -> IO (DatabaseHT)
trainHT words = do
hm <- HT.new
trainHT' words hm
where
trainHT' (x:y:[]) !hm = return hm
trainHT' (x:y:z:rem) !hm = do
let pair = STP x y
inCache <- HT.lookup hm pair
case inCache of
Nothing -> do
htN <- HT.new :: IO (DatabaseInnerHT)
HT.insert htN z $! 1
HT.insert hm pair $! htN
Just ht -> do
cvM <- HT.lookup ht z
case cvM of
Nothing -> HT.insert ht z 1
Just cv -> HT.insert ht z $! (cv+1)
trainHT' (y:z:rem) hm
main = do contents <- B.readFile "76.txt"
let bcont = B.split ' ' $ contents
print $ length bcont
let db = train4 $ bcont
print $ "Built a DB of " ++ show (M.size db) ++ " words"
--let db = trainHM2 $ bcont
--print $ "Built a DB of " ++ show (HM.size db) ++ " words"
--db <- trainHT $ (bcont)
--print $ "Built a DB"
Пространственная транслитерация C++ 11 (требует - сперва компилировать, не стесняйтесь чтобы исправить это):
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <tuple>
/*
Hash stuff here
Taken from https://stackoverflow.com/a/7111460/314327
*/
size_t hash_combiner(size_t left, size_t right) //replacable
{ return left^right;}
template<int index, class...types>
struct hash_impl {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
hash_impl<index-1, types...> next;
size_t b = std::hash<nexttype>()(std::get<index>(t));
return next(hash_combiner(a, b), t);
}
};
template<class...types>
struct hash_impl<0, types...> {
size_t operator()(size_t a, const std::tuple<types...>& t) const {
typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
size_t b = std::hash<nexttype>()(std::get<0>(t));
return hash_combiner(a, b);
}
};
namespace std {
template<class...types>
struct hash<std::tuple<types...>> {
size_t operator()(const std::tuple<types...>& t) {
const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
return hash_impl<begin, types...>()(1, t); //1 should be some largervalue
}
};
}
/*
Hash stuff end
*/
using namespace std;
/*
Split, from https://stackoverflow.com/a/236803/314327
*/
vector<string> &split(const string &s, char delim, vector<string> &elems) {
stringstream ss(s);
string item;
while (getline(ss, item, delim)) {
elems.push_back(item);
}
return elems;
}
vector<string> split(const string &s, char delim) {
vector<string> elems;
split(s, delim, elems);
return elems;
}
/*
Split end
*/
typedef tuple<string,string> STP;
unordered_map< STP,unordered_map< string,int > > train(vector<string> &words)
{
unordered_map< STP,unordered_map< string,int > > cache;
for(int i=0;i<words.size()-2;i++)
{
STP tup = make_tuple(words[i],words[i+1]);
auto it = cache.find(tup);
if(it!=cache.end())
{
auto it2 = it->second.find(words[i+2]);
if(it2!=it->second.end())
{
it2->second += 1;
}
else
it->second[words[i+2]] = 1;
}
else
{
unordered_map< string,int > cacheInner;
cacheInner[words[i+2]] = 1;
cache[tup] = cacheInner;
}
}
return cache;
}
int main()
{
ifstream ifs("76.txt");
stringstream buf;
buf << ifs.rdbuf();
string contents(buf.str());
auto words = split(contents,' ');
cout << words.size();
auto wordCache = train(words);
cout << "\nHashtable count " << wordCache.size();
cout << "\n";
return 0;
}
И результаты:
C++ (GCC 4.6.3)
$ g++ -O3 -fpermissive -std=c++0x cpptest.cpp -o cpptest
$ /usr/bin/time -f "%E" ./cpptest
1255153
Hashtable count 64442
0:01.02
Python (2,7)
$ /usr/bin/time -f "%E" ./pytest.py
Total of 1255153 splitted words
Built a db of length 64442
0:02.62
Haskell (GHC 7,4 .1) - "train4"
$ ghc -fllvm -O2 -rtsopts -fforce-recomp -funbox-strict-fields hasktest.hs -o hasktest
[1 of 1] Compiling Main (hasktest.hs, hasktest.o)
Linking hasktest ...
$ /usr/bin/time -f "%E" ./hasktest
1255153
"Built a DB of 64442 words"
0:06.35
Haskell - "trainHM2"
$ /usr/bin/time -f "%E" ./hasktest
1255153
"Built a DB of 64442 words"
0:04.23
Haskell - "trainHT" - (?, Которая близка к тому, что Python делает для словарей, я думаю), используя базовый вариант
$ /usr/bin/time -f "%E" ./hasktest
1255153
"Built a DB"
0:10.42
с использованием линейных или Кукушка для обеих таблиц
0:06.06
0:05.69
Использование кукушку для внешней таблицы и линейной на внутренней
0:04.17
показал Профилирование, что есть довольно много GC, поэтому, с + RTS -A256M
0:02.11
Для входных данных, я выбрал 76.txt, как указано в одном из ответов и дублируется весь текст 12 раз. Он должен составлять около 7 МБ.
Испытания проводились на Ubuntu 12.04 в контейнере VirtualBox с использованием единственного ядра i5-520M. Сделано более одного прогона, все результаты были довольно близкими.
Последний результат довольно отлично для этого microbenchmark, но есть что-нибудь еще, чтобы улучшить в коде, принимая во внимание, что:
- Кукушка & Linear может быть лучше подходит для этого набора данных, но «общее» решение Python хорошо идти без особого оптимизации в связи с этим,
- Valgrind сообщает, что версии Python C++ & занимают примерно
60MBsв то время как Haskell RTS сообщает в любом из125MBs(Cuckoo & Линейный) до409MBs(Базовая, большая куча) памяти для той же задачи. Не повлияет ли это на сборщик мусора в производственной среде? Можно ли реорганизовать код, чтобы он имел меньше памяти?
Update:
Я думаю, "сокращение мусора" является то, что я ищу. Я знаю, что Haskell работает не так, как это делает C++, но я хочу знать, можно ли уменьшить мусор, созданный в императивном коде, поскольку пример C++ потреблял половину памяти без каких-либо утечек пространства. Надеюсь, это будет улучшение в плане использования памяти и времени выполнения (поскольку будет меньше GC).
Update 2:
Вычисление длины при построении таблицы сократила объем памяти наверняка (вплоть до около 40MBs, на самом деле!), Что приводит к тому, GC, чтобы занять больше времени, что приводит к замедлению выполнения (из-за отбрасывания значений, которые были лениво прочитаны из списка, я полагаю?).
И да, операции hashtables занимают значительное количество времени. Я попробую подражать изменениям, чтобы увидеть, улучшится ли это дальше.
«есть ли что-нибудь еще, чтобы улучшить код» - большой вопрос. Можете быть более конкретными? Вы говорите, что есть много GC, но больше не говорите о том, что вы узнали из профилирования, или о том, какие вопросы возникли. – jberryman
Далеко не полный ответ, однако вы вынуждаете весь список слов печатать длину и сохраняете ее в памяти для конструкции dict. Я сохранил около 100 М от основного, большего размера кучи, не напечатав длину. Если вам это нужно, вы можете сделать значение длины параллельно со строкой словаря. –