On Nov 29, 3:15 pm, Bearophile <bearophileh...@lycos.com> wrote: > Maybe in your C++ code there's something that can be improved, this is > a 1:1 translation to D (V.1) language (using dlibs) and it's about 2.2 > times faster than the Psyco version:http://codepad.org/MQLj0ydB > Using a smarter usage of memory (that is avoiding all or most memory > allocations inside all loops), the performance difference will surely > grow.
Very interesting. Thanks. D code looks pretty neat. Btw D lang is among accepted langs there. Even if Py by 4x *slower* -- it's still a perfect Ok for it (C# will be much (much) slower than Python). Micro-optimizations. Of course, the best optimization would be to implement Suffix Tree: http://en.wikipedia.org/wiki/Trie Currently I hardly understand/know/read/etc its core idea. My algo is plainly stupid as soldier muddy boots. My C++ code: <BEGIN> #include <stdlib.h> #include <stdio.h> //#include <string.h> //#include <ctype.h> //#include <math.h> #include <time.h> #include <iostream> #include <vector> #include <string> using namespace std; int main() { clock_t start_time = clock(); freopen("88.txt", "rt", stdin); freopen("99.txt", "wt", stdout); int tcs; string s; cin >> tcs; while (tcs-- > 0) { cin >> s; int n = s.size(); s = s + ' '; vector< vector<int> > a(128); int ans = 0; for (int i = n - 1; i >= 0; --i) { int lev = 0; for (int st = (int)a[s[i]].size() - 1; st >= 0; --st) { int j = a[s[i]][st]; if (n - j <= lev) break; if (s[j + lev] != s[i + lev]) continue; if (s[j + lev / 2] != s[i + lev / 2]) continue; int k = 0; while (s[j + k] == s[i + k]) ++k; if (k > lev) lev = k; } a[s[i]].push_back(i); ans += n - i - lev; } cout << ans << endl; } cout << (clock() - start_time) / CLOCKS_PER_SEC << endl; return 0; } <END> -- http://mail.python.org/mailman/listinfo/python-list