Number of distinct substrings of a string [continuation]

Discussion in 'Python' started by n00m, Nov 29, 2009.

  1. n00m

    n00m Guest

    http://www.spoj.pl/problems/DISUBSTR/
    Got accepted both in C++(0.03s) and Python(0.12s).
    Don't know exactly how they benchmark solutions but
    my home tests proved Python is a fellow fast beast of C++.
    Quite unexpected (I expected Py would be by ~10 times slower).
    PS
    Both my codes are identical in their algorithms.


    Borland
    compiler
    (bcc32.exe) Python 2.5 + Psyco
    ================================
    1 1
    2 2
    13 13
    5 5
    9 9
    59078 59078
    1000 1000
    321000 321000
    =============================
    0.016 0.0150001049042 <--- exec times
    =============================

    ----------------------------------------------------
    My test input file:
    ----------------------------------------------------
    8

    a aa

    abbaz

    CCCCC ABABA

    fgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryududdisisisidfjfjnfnfgngnnghhhhhhhdeggrgtfgjtjdjjdjdjjryyryryudud


    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
    n00m, Nov 29, 2009
    #1
    1. Advertising

  2. n00m

    n00m Guest

    My Py solution:

    =====================================================

    import psyco
    psyco.full()

    def foo(s):
    n = len(s)
    s = s + ' '
    a = [[] for i in xrange(128)]
    ans = 0
    for i in xrange(n - 1, -1, -1):
    lev = 0
    for st in xrange(len(a[ord(s)]) - 1, -1, -1):
    j = a[ord(s)][st]
    if (n - j <= lev):
    break
    if (s[j + lev] != s[i + lev]):
    continue
    if (s[j + lev / 2] != s[i + lev / 2]):
    continue
    k = 0
    while (s[j + k] == s[i + k]):
    k += 1
    if (k > lev):
    lev = k
    a[ord(s)] +=
    ans += n - i - lev
    return ans


    from time import time
    t = time()

    import sys
    sys.stdin = open('D:/88.txt', 'rt')
    f = sys.stdin.read().split()
    sys.stdin.close()

    z = open('D:/99.txt', 'wt')

    for tc in range(int(f[0])):
    s = f[tc + 1]
    print >> z, foo(s)

    print >> z, time() - t
    z.close()

    ========================================================
    n00m, Nov 29, 2009
    #2
    1. Advertising

  3. n00m

    n00m Guest

    This worked out in 5.28s
    Imo it's not that *much* slower
    (of course, Psyco can't help here)
    ===================================

    import itertools
    def subs(s):
    return len(set(itertools.chain(
    s[i:j]
    for i in xrange(len(s))
    for j in xrange(i, len(s)+1)))) - 1


    from time import time
    t = time()

    import sys
    sys.stdin = open('D:/88.txt', 'rt')
    f = sys.stdin.read().split()
    sys.stdin.close()

    z = open('D:/99.txt', 'wt')

    for tc in range(int(f[0])):
    s = f[tc + 1]
    print >> z, subs(s)

    print >> z, time() - t
    z.close()

    ==================================================
    n00m, Nov 29, 2009
    #3
  4. n00m

    Bearophile Guest

    n00m:
    > This worked out in 5.28s
    > Imo it's not that *much* slower
    > (of course, Psyco can't help here)


    There's no need of a chain here, so you can rewrite this:

    import itertools
    def subs(s):
    return len(set(itertools.chain(
    s[i:j]
    for i in xrange(len(s))
    for j in xrange(i, len(s)+1)))) - 1

    as:

    def subs(s):
    return len(set(s[i:j] for i in xrange(len(s))
    for j in xrange(i, len(s)+1))) - 1


    Psyco helps a little (about 10% on my PC) if you use it like this:

    from time import time
    import psyco; psyco.full()

    def main():
    t = time()
    fin = open("input.txt")
    fout = open("output.txt", "w")
    fin.next()
    for line in fin:
    r = set()
    s = line.rstrip()
    len_s = len(s)
    for i in xrange(len_s):
    for j in xrange(i, len_s + 1):
    r.add(s[i : j])
    print >> fout, len(r) - 1
    fout.close()
    print time() - t

    main()

    Bye,
    bearophile
    Bearophile, Nov 29, 2009
    #4
  5. n00m

    Bearophile Guest

    n00m:
    > My Py solution:
    > ...


    Cute. You can replace:
    a[ord(s)] +=
    With:
    a[ord(s)].append(i)

    If you want to micro-optimize this with Psyco may be a little faster:
    (lev >> 1)
    Than:
    lev // 2

    But to increase speed it's usually better to reduce memory
    allocations. So you can try to find a way to pull this out of the
    function:
    a = [[] for i in xrange(128)]
    And to avoid a true append:
    a[ord(s)] +=

    (There are many ways to avoid an append. One of them is to have an
    already allocated list/array and just bump forward an index variable
    that starts from 0. This is worth doing especially when you use
    Psyco).

    Bye,
    bearophile
    Bearophile, Nov 29, 2009
    #5
  6. n00m

    Bearophile Guest

    n00m:
    > my home tests proved Python is a fellow fast beast of C++.
    > Quite unexpected (I expected Py would be by ~10 times slower).
    > PS
    > Both my codes are identical in their algorithms.


    > =============================
    > 0.016         0.0150001049042   <--- exec times


    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.

    Bye,
    bearophile
    Bearophile, Nov 29, 2009
    #6
  7. n00m

    n00m Guest

    On Nov 29, 3:15 pm, Bearophile <> 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].size() - 1; st >= 0; --st) {
    int j = a[s][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].push_back(i);
    ans += n - i - lev;
    }
    cout << ans << endl;
    }

    cout << (clock() - start_time) / CLOCKS_PER_SEC << endl;

    return 0;
    }
    <END>
    n00m, Nov 29, 2009
    #7
  8. n00m

    n00m Guest

    n00m, Nov 29, 2009
    #8
  9. n00m

    n00m Guest

    Tested both my codes against
    a random string of length = 10000.

    ===========================================

    from random import choice
    s = ''
    for i in xrange(10000):
    s += choice(('a','b','c','d','e','f'))

    ===========================================

    C++: ~0.28s
    Python: ~0.48s

    PS
    I suspect that building of Suffix Tree would
    be a big exec.time-consuming overhead
    n00m, Nov 29, 2009
    #9
  10. n00m

    Bearophile Guest

    n00m:

    > I suspect that building of Suffix Tree would
    > be a big exec.time-consuming overhead


    In C/D/C++ there are ways to allocate memory in smarter ways, using
    pools, arenas, stacks, freelists, etc. With that, using a compact
    encoding of tree nodes (there are many different tricks to reduce
    space used by a suffix tree), you can go fast enough. Probably a basic
    implementation too will suffice in many cases :)

    Anyway, you may try a pure-Python2.x implementation:
    http://suffixtree.googlecode.com/files/suffixtree-0.1.py
    If you find time & will to try to use that (or similar code) to
    improve your Python solution to the problem 99, you can show us the
    code here...

    Bye,
    bearophile
    Bearophile, Nov 29, 2009
    #10
  11. n00m

    n00m Guest

    On Nov 29, 11:43 pm, Bearophile <> wrote:
    > Anyway, you may try a pure-Python2.x implementation:http://suffixtree.googlecode.com/files/suffixtree-0.1.py


    Ouch, Bearie... 214 lines of code are there.
    Ok.. I tested it.
    Firstly I replaced all "print " with "pass##print "
    (aiming to avoid intensive printing from inside of the code).

    Then I left in its final part only building of suffix trees.

    ==================================================================
    ....
    ....
    ....

    from time import time
    t = time()

    import sys
    sys.stdin = open('D:/88.txt', 'rt')
    f = sys.stdin.read().split()
    sys.stdin.close()

    z = open('D:/99.txt', 'wt')

    for tc in range(int(f[0])):
    s = f[tc + 1]
    test_str = s + '$'
    POSITIVE_INFINITY = len(test_str) - 1
    suffix_tree = SuffixTree(test_str)
    print >> z, 'len(s) =', len(s)

    print >> z, 'time =', time() - t
    z.close()
    ============================================================

    Output:
    ============================================================
    len(s) = 1000
    len(s) = 1000
    len(s) = 10000
    time = 0.641000032425
    ============================================================

    0.64s > 0.48s (of my algo)
    I.e. the code can't help in my very special and narrow case.

    But of course it is worthy to be studied and memoized.
    E.g.:
    from huge string "s" we built its Suffix Tree.
    Now we are given arbitrary string "ss".
    Task: to find the largest its prefix occured in "s",
    traversing its Suffix Tree.
    n00m, Nov 30, 2009
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tung Chau
    Replies:
    1
    Views:
    468
    SM Ryan
    Aug 6, 2004
  2. Hal Vaughan

    Distinct ID Number Per Object?

    Hal Vaughan, Jun 16, 2007, in forum: Java
    Replies:
    54
    Views:
    1,275
    Roedy Green
    Jun 29, 2007
  3. Peng Yu
    Replies:
    0
    Views:
    227
    Peng Yu
    Oct 24, 2009
  4. Hicham Mouline
    Replies:
    1
    Views:
    390
    Kai-Uwe Bux
    Apr 11, 2010
  5. Jan Biel
    Replies:
    2
    Views:
    163
    GreenLight
    Apr 2, 2004
Loading...

Share This Page