HOPE: The Ease Of Python With The Speed Of C++

[pal666]

I am not sure what you mean by this. You have to iterate over the string to get the counts in the first place. In most cases it would be faster to find the unique values first, so you could do something like this:

def getmin(s):
    return len(s) - max(s.count(ch) for ch in set(s))

But at the very least you still need to go through each character found in "s" and find how many times that character occurs somehow.

but you need to iterate over string only once. while python-damaged people write code, which iterates over string in for loop and then for each iteration iterates again in s.count()

[TheBlackCat]

but you need to iterate over string only once. while python-damaged people write code, which iterates over string in for loop and then for each iteration iterates again in s.count()

You would either need to iterate over the string twice, or iterate over the string and a sequence of characters that have been found so far. You would need two iterators either way.

From what I can tell, your approach would be something like this:

def getmin(s):
    count = {}
    for ch in s:
        if ch in count:
            count[ch] += 1
        else:
            count[ch] = 1
    return len(s) - max(count.values())

or this:

def getmin(s):
    letters = []
    count = []
    for ch in s:
        try:
            ind = letters.index(count)
        except:
            letters.append(ch)
            count.append(1)
        else:
            letters[ind] += 1
    return len(s) - max(count)

But the issue is that you still have to iterate over "count" or "letters" to determine if the characters is already present.

[kigurai]

my "like that" related to syntax. i hope you aren't going to insist on using variable before introducing it.
http://www.boost.org/doc/libs/1_56_0...roduction.html

First of all that is boost, and not standard C++.
Second, I don't think that I immediately understood how that was supposed to work.
Can you please, for clarity, just take the Python example and give that as a C++ + boost version?
Note, I am not being snarky, I am genuinely curious since everything that makes C++ easier to work with is a win in my book.

[pal666]

You would either need to iterate over the string twice, or iterate over the string and a sequence of characters that have been found so far. You would need two iterators either way.

you seem to not understand the difference between two iterations(which i explicitly mentioned) and N iterations, where N is number of characters in input

But the issue is that you still have to iterate over "count" or "letters" to determine if the characters is already present.

no, you don't
if you are using 8 bit strings, you can use fixed size array of 256 counts
if you are using wide strings, you are probably better off with associative array which uses either tree or hash, i.e. O(log N) access or even better

[pal666]

First of all that is boost, and not standard C++.
Second, I don't think that I immediately understood how that was supposed to work.
Can you please, for clarity, just take the Python example and give that as a C++ + boost version?
Note, I am not being snarky, I am genuinely curious since everything that makes C++ easier to work with is a win in my book.

first of all, boost is perfectly standard c++.
second, i don't think i immediately understood, how python example was supposed to work.

[TheBlackCat]

if you are using wide strings, you are probably better off with associative array which uses either tree or hash, i.e. O(log N) access or even better

If you looked at my examples you would see that is exactly what I did in the first and second case. You are right, technically that is not iterating over a sequence. But it is still not O(n) performance no matter what you do.

[pal666]

Can you please, for clarity, just take the Python example and give that as a C++ + boost version?

s.size ( ) - * boost :: max_element ( s | boost :: adaptors :: transformed ( std :: function < std :: size_t ( char ) > { [ & ] ( char c ) { return boost :: count ( s, c ); } } ) );

[erendorn]

First of all that is boost, and not standard C++.
Second, I don't think that I immediately understood how that was supposed to work.
Can you please, for clarity, just take the Python example and give that as a C++ + boost version?
Note, I am not being snarky, I am genuinely curious since everything that makes C++ easier to work with is a win in my book.

Note that there is a range-based for loop in C++11, as shown in my previous post.
There are a lot of good things in C++11 (auto, smart pointers, new keywords such as null_ptr to replace macros, etc...).
The one thing I find lacking in C++ is modules, because, let's be serious, #include sucks.

[pal666]

If you looked at my examples you would see that is exactly what I did in the first and second case. You are right, technically that is not iterating over a sequence. But it is still not O(n) performance no matter what you do.

well, i can't be sure whether you tried to iterate with quadratic complexity in second example or not, because it clearly does not work (you are trying to index one array with another). but it could have compiled without errors in this toy language

[TheBlackCat]

well, i can't be sure whether you tried to iterate with quadratic complexity in second example or not, because it clearly does not work (you are trying to index one array with another). but it could have compiled without errors in this toy language

Sorry, that is a typo. I screwed up the code tags and had to rush to fix it before the time limit expired. It should be "ch", not "count".

But that was my third example, my first was from the earlier post.