1
Я пытаюсь написать простой лексер в clojure. Пока что он распознает только выделенные пробелы.Медленный лексер в clojure
(refer 'clojure.set :only '[union])
(defn char-range-set
"Generate set containing all characters in the range [from; to]"
[from to]
(set (map char (range (int from) (inc (int to))))))
(def ident-initial (union (char-range-set \A \Z) (char-range-set \a \z) #{\_}))
(def ident-subseq (union ident-initial (char-range-set \0 \9)))
(defn update-lex [lex token source]
(assoc (update lex :tokens conj token) :source source))
(defn scan-identifier [lex]
(assert (ident-initial (first (:source lex))))
(loop [[c & cs :as source] (rest (:source lex))
value [(first (:source lex))]]
(if (ident-subseq c)
(recur cs (conj value c))
(update-lex lex {:type :identifier :value value} source))))
(defn scan [{tokens :tokens [c & cs :as source] :source :as lex}]
(cond
(Character/isWhitespace c) (assoc lex :source cs)
(ident-initial c) (scan-identifier lex)))
(defn tokenize [source]
(loop [lex {:tokens [] :source source}]
(if (empty? (:source lex))
(:tokens lex)
(recur (scan lex)))))
(defn measure-tokenizer [n]
(let [s (clojure.string/join (repeat n "abcde "))]
(time (tokenize s))
(* n (count "abcde "))))
Lexer обрабатывает около 6 миллионов символов в течение 15 секунд.
=> (measure-tokenizer 1000000)
"Elapsed time: 15865.909399 msecs"
После этого я преобразовал все карты и векторы в переходные процессы. Это не улучшило.
Кроме того, я реализовал аналогичный алгоритм в C++. Для одного входа требуется всего 0,2 секунды.
Мой вопрос: Как я могу улучшить свой код? Возможно, я неправильно использую структуры данных clojure?
UPDATE:
Так вот мой код C++.
#include <iostream>
#include <vector>
#include <chrono>
#include <unordered_set>
#include <cstdlib>
#include <string>
#include <cctype>
using namespace std;
struct Token
{
enum { IDENTIFIER = 1 };
int type;
string value;
};
class Lexer
{
public:
Lexer(const std::string& source)
: mSource(source)
, mIndex(0)
{
initCharSets();
}
std::vector<Token> tokenize()
{
while (mIndex < mSource.size())
{
scan();
}
return mResult;
}
private:
void initCharSets()
{
for (char c = 'a'; c <= 'z'; ++c)
mIdentifierInitial.insert(c);
for (char c = 'A'; c <= 'Z'; ++c)
mIdentifierInitial.insert(c);
mIdentifierInitial.insert('_');
mIdentifierSubsequent = mIdentifierInitial;
for (char c = '0'; c <= '9'; ++c)
mIdentifierSubsequent.insert(c);
}
void scan()
{
skipSpaces();
if (mIndex < mSource.size())
{
if (mIdentifierInitial.find(mSource[mIndex]) != mIdentifierInitial.end())
{
scanIdentifier();
}
mResult.push_back(mToken);
}
}
void scanIdentifier()
{
size_t i = mIndex;
while ((i < mSource.size()) && (mIdentifierSubsequent.find(mSource[i]) != mIdentifierSubsequent.end()))
++i;
mToken.type = Token::IDENTIFIER;
mToken.value = mSource.substr(mIndex, i - mIndex);
mIndex = i;
}
void skipSpaces()
{
while ((mIndex < mSource.size()) && std::isspace(mSource[mIndex]))
++mIndex;
}
unordered_set<char> mIdentifierInitial;
unordered_set<char> mIdentifierSubsequent;
string mSource;
size_t mIndex;
vector<Token> mResult;
Token mToken;
};
void measureBigString(int n)
{
std::string substri = "jobbi ";
std::string bigstr;
for (int i =0 ;i < n;++i)
bigstr += substri;
Lexer lexer(bigstr);
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
lexer.tokenize();
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << n << endl;
std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() <<std::endl;
std::cout << "\n\n\n";
}
int main()
{
measureBigString(1000000);
return 0;
}
Включите '* warning-on-reflection *', и вы увидите, что вы должны изменить его на: '(Character/isWhitespace^char c)', это дает ускорение x7. – ClojureMostly
Ну, это изменение дает ускорение x3-x5, на самом деле. Но это неплохо. – Hanik
Можете ли вы показать нам код на C++? – ClojureMostly