Why does this O(n^2) code execute faster than O(n)? [duplicate]

up vote
19
down vote

favorite

This question already has an answer here:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

6 answers

I have written code for two approaches to find out the first unique character in a string on LeetCode.

Problem Statement:
Given a string, find the first non-repeating
character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

Approach 1 (O(n)) (correct me if I am wrong):

class Solution {

    public int firstUniqChar(String s) {



        HashMap<Character,Integer> charHash = new HashMap<>();



        int res = -1;



        for (int i = 0; i < s.length(); i++) {



            Integer count = charHash.get(s.charAt(i));



            if (count == null){

                charHash.put(s.charAt(i),1);

            }

            else {

                charHash.put(s.charAt(i),count + 1);

            }

        }



        for (int i = 0; i < s.length(); i++) {



            if (charHash.get(s.charAt(i)) == 1) {

                res = i;

                break;

            }

        }



        return res;

    }

}

Approach 2 (O(n^2)):

class Solution {

    public int firstUniqChar(String s) {



        char a = s.toCharArray();

        int res = -1;



        for(int i=0; i<a.length;i++){

            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {

                res = i;

                break;

            }

        }

        return res;

    }

}

In approach 2, I think the complexity should be O(n^2) since indexOf executes in O(n*1) here.

But when I execute both the solutions on LeetCode I get runtime 19 ms for approach 2 and 92 ms for approach 1. I am confused; why does that happen?

I suppose LeetCode tests for both small and large input values for best, worst and average cases.

Update:

I am aware of the fact that O(n^2 algorithms) can perform better for certain n < n1. In this question I wanted to understand why that is happening in this case. i.e. which part of Approach 1 makes it slower.

LeetCode link to the question

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

marked as duplicate by Mike 'Pomax' Kamermans, BJ Myers, Michael java
Users with the java badge can single-handedly close java questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
9 hours ago

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3

What's your reasoning the second solution is n^2? Both indexOfand lastIndexOf iterate the string at most once, so total complexity is 2*n for string length n. n^2 would mean you iterate the string once for each of its characters.
– daniu
yesterday

3

@daniu and thats' what he's doing: for(int i=0; i<a.length;i++){
– JB Nizet
yesterday

2

indexOf(a[i]) is redundant, the test can be i == s.lastIndexOf(a[i])
– Nathan Hughes
yesterday

4

@NathanHughes For input = "cc", if I do not use indexOf, the code will return 1, while the expected answer is -1 since the string has no unique characters.
– Nivedita
yesterday

2

O() is a measure of how well an algorithm scales, not how fast it is.
– ikegami
23 hours ago

|
show 5 more comments

up vote
19
down vote

favorite

This question already has an answer here:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

6 answers

I have written code for two approaches to find out the first unique character in a string on LeetCode.

Problem Statement:
Given a string, find the first non-repeating
character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

Approach 1 (O(n)) (correct me if I am wrong):

class Solution {

    public int firstUniqChar(String s) {



        HashMap<Character,Integer> charHash = new HashMap<>();



        int res = -1;



        for (int i = 0; i < s.length(); i++) {



            Integer count = charHash.get(s.charAt(i));



            if (count == null){

                charHash.put(s.charAt(i),1);

            }

            else {

                charHash.put(s.charAt(i),count + 1);

            }

        }



        for (int i = 0; i < s.length(); i++) {



            if (charHash.get(s.charAt(i)) == 1) {

                res = i;

                break;

            }

        }



        return res;

    }

}

Approach 2 (O(n^2)):

class Solution {

    public int firstUniqChar(String s) {



        char a = s.toCharArray();

        int res = -1;



        for(int i=0; i<a.length;i++){

            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {

                res = i;

                break;

            }

        }

        return res;

    }

}

In approach 2, I think the complexity should be O(n^2) since indexOf executes in O(n*1) here.

But when I execute both the solutions on LeetCode I get runtime 19 ms for approach 2 and 92 ms for approach 1. I am confused; why does that happen?

I suppose LeetCode tests for both small and large input values for best, worst and average cases.

Update:

LeetCode link to the question

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

marked as duplicate by Mike 'Pomax' Kamermans, BJ Myers, Michael java
Users with the java badge can single-handedly close java questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
9 hours ago

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3

What's your reasoning the second solution is n^2? Both indexOfand lastIndexOf iterate the string at most once, so total complexity is 2*n for string length n. n^2 would mean you iterate the string once for each of its characters.
– daniu
yesterday

3

@daniu and thats' what he's doing: for(int i=0; i<a.length;i++){
– JB Nizet
yesterday

2

indexOf(a[i]) is redundant, the test can be i == s.lastIndexOf(a[i])
– Nathan Hughes
yesterday

4

@NathanHughes For input = "cc", if I do not use indexOf, the code will return 1, while the expected answer is -1 since the string has no unique characters.
– Nivedita
yesterday

2

O() is a measure of how well an algorithm scales, not how fast it is.
– ikegami
23 hours ago

|
show 5 more comments

up vote
19
down vote

favorite

This question already has an answer here:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

6 answers

I have written code for two approaches to find out the first unique character in a string on LeetCode.

Problem Statement:
Given a string, find the first non-repeating
character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

Approach 1 (O(n)) (correct me if I am wrong):

class Solution {

    public int firstUniqChar(String s) {



        HashMap<Character,Integer> charHash = new HashMap<>();



        int res = -1;



        for (int i = 0; i < s.length(); i++) {



            Integer count = charHash.get(s.charAt(i));



            if (count == null){

                charHash.put(s.charAt(i),1);

            }

            else {

                charHash.put(s.charAt(i),count + 1);

            }

        }



        for (int i = 0; i < s.length(); i++) {



            if (charHash.get(s.charAt(i)) == 1) {

                res = i;

                break;

            }

        }



        return res;

    }

}

Approach 2 (O(n^2)):

class Solution {

    public int firstUniqChar(String s) {



        char a = s.toCharArray();

        int res = -1;



        for(int i=0; i<a.length;i++){

            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {

                res = i;

                break;

            }

        }

        return res;

    }

}

In approach 2, I think the complexity should be O(n^2) since indexOf executes in O(n*1) here.

But when I execute both the solutions on LeetCode I get runtime 19 ms for approach 2 and 92 ms for approach 1. I am confused; why does that happen?

I suppose LeetCode tests for both small and large input values for best, worst and average cases.

Update:

LeetCode link to the question

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

This question already has an answer here:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

6 answers

I have written code for two approaches to find out the first unique character in a string on LeetCode.

Problem Statement:
Given a string, find the first non-repeating
character in it and return it's index. If it doesn't exist, return -1.

Sample Test Cases:

s = "leetcode" return 0.

s = "loveleetcode", return 2.

Approach 1 (O(n)) (correct me if I am wrong):

class Solution {

    public int firstUniqChar(String s) {



        HashMap<Character,Integer> charHash = new HashMap<>();



        int res = -1;



        for (int i = 0; i < s.length(); i++) {



            Integer count = charHash.get(s.charAt(i));



            if (count == null){

                charHash.put(s.charAt(i),1);

            }

            else {

                charHash.put(s.charAt(i),count + 1);

            }

        }



        for (int i = 0; i < s.length(); i++) {



            if (charHash.get(s.charAt(i)) == 1) {

                res = i;

                break;

            }

        }



        return res;

    }

}

Approach 2 (O(n^2)):

class Solution {

    public int firstUniqChar(String s) {



        char a = s.toCharArray();

        int res = -1;



        for(int i=0; i<a.length;i++){

            if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {

                res = i;

                break;

            }

        }

        return res;

    }

}

In approach 2, I think the complexity should be O(n^2) since indexOf executes in O(n*1) here.

But when I execute both the solutions on LeetCode I get runtime 19 ms for approach 2 and 92 ms for approach 1. I am confused; why does that happen?

I suppose LeetCode tests for both small and large input values for best, worst and average cases.

Update:

LeetCode link to the question

This question already has an answer here:

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

6 answers

java time-complexity big-o

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

edited 15 hours ago

Peter Mortensen

13.3k1983111

edited 15 hours ago

Peter Mortensen

13.3k1983111

edited 15 hours ago

Peter Mortensen

13.3k1983111

asked yesterday

Nivedita

1,0611235

asked yesterday

Nivedita

1,0611235

asked yesterday

Nivedita

1,0611235

marked as duplicate by Mike 'Pomax' Kamermans, BJ Myers, Michael java
Users with the java badge can single-handedly close java questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
9 hours ago

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

marked as duplicate by Mike 'Pomax' Kamermans, BJ Myers, Michael java
Users with the java badge can single-handedly close java questions as duplicates and reopen them as needed.

StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;

$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');

$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
9 hours ago

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3

What's your reasoning the second solution is n^2? Both indexOfand lastIndexOf iterate the string at most once, so total complexity is 2*n for string length n. n^2 would mean you iterate the string once for each of its characters.
– daniu
yesterday

3

@daniu and thats' what he's doing: for(int i=0; i<a.length;i++){
– JB Nizet
yesterday

2

indexOf(a[i]) is redundant, the test can be i == s.lastIndexOf(a[i])
– Nathan Hughes
yesterday

4

@NathanHughes For input = "cc", if I do not use indexOf, the code will return 1, while the expected answer is -1 since the string has no unique characters.
– Nivedita
yesterday

2

O() is a measure of how well an algorithm scales, not how fast it is.
– ikegami
23 hours ago

|
show 5 more comments

3

What's your reasoning the second solution is n^2? Both indexOfand lastIndexOf iterate the string at most once, so total complexity is 2*n for string length n. n^2 would mean you iterate the string once for each of its characters.
– daniu
yesterday

3

@daniu and thats' what he's doing: for(int i=0; i<a.length;i++){
– JB Nizet
yesterday

2

indexOf(a[i]) is redundant, the test can be i == s.lastIndexOf(a[i])
– Nathan Hughes
yesterday

4

@NathanHughes For input = "cc", if I do not use indexOf, the code will return 1, while the expected answer is -1 since the string has no unique characters.
– Nivedita
yesterday

2

O() is a measure of how well an algorithm scales, not how fast it is.
– ikegami
23 hours ago

What's your reasoning the second solution is n^2? Both indexOfand lastIndexOf iterate the string at most once, so total complexity is 2*n for string length n. n^2 would mean you iterate the string once for each of its characters.
– daniu
yesterday

@daniu and thats' what he's doing: for(int i=0; i<a.length;i++){
– JB Nizet
yesterday

indexOf(a[i]) is redundant, the test can be i == s.lastIndexOf(a[i])
– Nathan Hughes
yesterday

@NathanHughes For input = "cc", if I do not use indexOf, the code will return 1, while the expected answer is -1 since the string has no unique characters.
– Nivedita
yesterday

O() is a measure of how well an algorithm scales, not how fast it is.
– ikegami
23 hours ago

|
show 5 more comments

7 Answers
7

active

oldest

votes

up vote
79
down vote

Consider:

f₁(n) = n²

f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

answered yesterday

arshajii

99.4k18178249

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

add a comment |

up vote
30
down vote

For very short strings e.g. single character the cost of creating HashMap, re-sizing it, looking up entries while boxing and unboxing of char into Character might overshadow the cost of String.indexOf(), which is probably considered hot and inlined by JVM either way.

Another reason might be the cost of RAM access. With additional HashMap, Character and Integer objects involved in a lookup there might be need for additional access to and from RAM. Single access is ~100 ns and this can add up.

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

1

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

2

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

6

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

|
show 1 more comment

up vote
15
down vote

Big O notation is a theoretical measure of the manner in which an algorithm scales in terms of memory consumption or computational time with N - the number of elements or dominant operations, and always as N->Infinity.

In practice, N in your example is fairly small. Whilst adding an element to a hash-table is generally considered to be amortised O(1), it might also result in a memory allocation (again, depending on the the design of your hash-table). This may not be O(1) - and may also result in the process making a system call to the kernel for another page.

Taking the O(n^2) solution - the string in a will quickly find itself in cache and will likely run uninterrupted. The cost of a single memory allocation will likely be higher than the pair of nested loops.

In practice with modern CPU architectures, where reads form cache are orders of magnitude faster than those from main memory, N will be quite large before using a theoretically optimal algorithm outperforms a linear data structure and linear searching. Binary trees are particularly bad news for cache efficiency.

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

edited yesterday

answered yesterday

marko

7,65142338

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

add a comment |

up vote
10
down vote

O(n²) is only the worst case time complexity of the second approach.

For strings such as bbbbbb...bbbbbbbbbaaaaaaaaaaa...aaaaaaaaaaa where there are x b's and x a's, each loop iteration takes about x steps to determine the index, hence the total performed steps is about 2x². For x about 30000, it would take about 1~2 second(s), while the other solution would perform much better.

On Try it online, this benchmark computes that approach 2 is about 50 times slower than approach 1 for the string above. For larger x, the difference is even larger (approach 1 takes about 0.01 second, approach 2 takes a few seconds)

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

This is true assuming Java uses the naive string searching algorithm, which searches the character one-by-one until a match is found, then immediately returns. The time complexity of the search is the number of considered characters.

It can be easily proven (the proof is similar to this Math.SE post - Expected value of the number of flips until the first head) that the expected position of a particular character in a uniform independent string over the alphabet {a,b,c,...,z} is O(1). Therefore, each indexOf and lastIndexOf call runs in expected O(1) time, and the whole algorithm takes expected O(n) time.

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

edited yesterday

answered yesterday

user202729

1,0613719

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

add a comment |

up vote
3
down vote

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

answered yesterday

yaccob

59359

add a comment |

up vote
0
down vote

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>

#include <string_view>

int first_unique_char(char s, int s_len) noexcept {

    std::map<char, int> char_hash;

    int res = -1;

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        auto r = char_hash.find(c);

        if (r == char_hash.end())

            char_hash.insert(std::pair<char, int>(c,1));

        else {

            int new_val = r->second + 1;

            char_hash.erase(c);

            char_hash.insert(std::pair<char, int>(c, new_val));

        }

    }

    for (int i = 0; i < s_len; i++)

        if (char_hash.find(s[i])->second == 1) {

            res = i;

            break;

        }

    return res;

}

int first_unique_char2(char s, int s_len) noexcept {

    int res = -1;

    std::string_view str = std::string_view(s, s_len);

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        if (str.find_first_of(c) == str.find_last_of(c)) {

            res = i;

            break;

        }

    }

    return res;

}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())

        char_hash.insert(std::pair<char, int>(c,1));

    else {

        int new_val = r->second + 1;

        char_hash.erase(c);

        char_hash.insert(std::pair<char, int>(c, new_val));

    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.

edited yesterday

answered yesterday

MCCCS

3761727

2

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

add a comment |

up vote
0
down vote

First, complexity analysis does not tell you an awful lot. It used to tell you how algorithms would -- in theory -- compare as the size of the problem grows to large numbers (towards infinity, if you will), and to some extent it still does.

However, complexity analysis makes assumptions that were only half-true some 30-40 years ago and are not in any way true nowadays (such as e.g. all ops are the same, all accesses are the same). We live in a world in which constant factors are huge, and not all operations are the same, not even remotely. Insofar, it has to be considered with very great care, in no case can you assume "this is O(N) so it will be faster". That's a huge fallacy.

For small numbers, looking at "big O" is mostly pointless, but even for large numbers, be aware that the constant factor can play a huge, dominating role. No, the constant factor is not zero, and it is not neglegible. Do not ever assume that.

The theoretically super awesome algorithm which, for example, finds something in a billion elements with only 20 accesses can be much slower than a "bad" algorithm that takes 200,000 accesses -- if in the first case each of the 20 accesses causes a page fault with a disk seek (each of which is worth some hundred million operations). Theory and practice do not always go hand in hand here.

Second, despite being idiomatic and generally looking like good idea (it's O(1), eh?), using a hash map is just bad in many cases. Not in every case, but this is such a case. Compare what the two code snippets are doing.

The O(N²) one converts a moderately small string to a character array once (which basically costs zero) and then repeatedly accesses that array in a linear fashion. Wich is pretty much the fastest thing a computer is able to do, even in Java. Yes, Java is agnostic of any such thing as memory or caches, but that cannot change the fact that these things exist. Locally accessing small/moderate amounts of data in a mostly linear fashion is fast.

The other snippet inserts characters into a hashmap, allocating a data structure for every character. Yes, dynamic allocations in Java are not that expensive, but still allocations are nowhere near free, and memory accesses become non-contiguous.

Then, a hash function is calculated. This is something that is often overlooked with hash maps. For a single character, this is (hopefully) a cheap operation, but it is nowhere near free^[1]. Then, the data structure is in some way inserted into a bucket (which is technically nothing but another non-coherent memory access). Now, there's a fair chance of a collision, in which case something else must be done (chaining, rehashing, whatever).

Later, values are being read from the hash map again, which again involves calling the hash function, looking up the bucket, possibly traversing a list, and doing a comparison at each node (this is necessary due to the possibility of collisions).

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

^[1] Not an issue here for single-character keys but still, fun fact: People often talk of hash maps in terms of O(1) which already isn't true with e.g. chaining, but are then surprised that actually hashing the key is O(N) in respect of the length of the key. Which may very well be noticeable.

answered 9 hours ago

Damon

50.2k1496152

add a comment |

7 Answers
7

active

oldest

votes

7 Answers
7

active

oldest

votes

up vote
79
down vote

Consider:

f₁(n) = n²

f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

answered yesterday

arshajii

99.4k18178249

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

add a comment |

up vote
79
down vote

Consider:

f₁(n) = n²

f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

answered yesterday

arshajii

99.4k18178249

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

add a comment |

up vote
79
down vote

Consider:

f₁(n) = n²

f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

answered yesterday

arshajii

99.4k18178249

Consider:

f₁(n) = n²

f₂(n) = n + 1000

Clearly f₁ is O(n²) and f₂ is O(n). For a small input (say, n=5), we have f₁(n) = 25 but f₂(n) > 1000.

Just because one function (or time complexity) is O(n) and another is O(n²) doesn't mean that the former is smaller for all values of n, just that there is some n beyond which this will be the case.

answered yesterday

arshajii

99.4k18178249

answered yesterday

arshajii

99.4k18178249

answered yesterday

arshajii

99.4k18178249

answered yesterday

arshajii

99.4k18178249

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

add a comment |

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

Arguing that n is too small can be misleading. Even with larger n, if the strings are still random, (according to my answer) solution 2 would still perform better. In the worst case for n (string size) as small as 30000 (leetcode tests with much larger n!) the second approach is already about 50-100 times worse.
– user202729
14 hours ago

add a comment |

up vote
30
down vote

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

1

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

2

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

6

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

|
show 1 more comment

up vote
30
down vote

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

1

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

2

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

6

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

|
show 1 more comment

up vote
30
down vote

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

Take a look at Bjarne Stroustrup: Why you should avoid Linked Lists. This lecture illustrates that performance is not the same as complexity and memory access can be a killer for an algorithm.

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

edited 15 hours ago

Peter Mortensen

13.3k1983111

edited 15 hours ago

Peter Mortensen

13.3k1983111

edited 15 hours ago

Peter Mortensen

13.3k1983111

answered yesterday

Karol Dowbecki

13k62745

answered yesterday

Karol Dowbecki

13k62745

answered yesterday

Karol Dowbecki

13k62745

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

1

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

2

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

6

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

|
show 1 more comment

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

1

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

2

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

6

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

So, will it be correct to say that - theoretically approach 1 is faster but practically approach 2 has a better performance?
– Nivedita
yesterday

@Nivedita for some cases, yes. Theoretical approach is not really faster, it just has a better complexity which is a different measure.
– Karol Dowbecki
yesterday

@Nivedita - What you said is not true in general.
– Stephen C
yesterday

Of course, if you're doing a Cracking the coding interview style question, N is always infinitely large ;). I'd be impressed with a candidate who, without prompting, told me how theory doesn't quite align with reality.
– marko
yesterday

@Nivedita you're missing the point: O(n) is based on what happens as n gets large. Approach 1 isn't just faster in theory, approach 1 won't cause your application to hang for larger values of n then approach 2. Always, always, always think "how will this break? what can go wrong?". Never, never, never focus on the happy path.
– Jared Smith
yesterday

|
show 1 more comment

up vote
15
down vote

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

edited yesterday

answered yesterday

marko

7,65142338

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

add a comment |

up vote
15
down vote

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

edited yesterday

answered yesterday

marko

7,65142338

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

add a comment |

up vote
15
down vote

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

edited yesterday

answered yesterday

marko

7,65142338

[Edit] it's Java: The hash table contains references to boxed java.lang.Character object. Every single addition will result in a memory allocation

edited yesterday

answered yesterday

marko

7,65142338

edited yesterday

answered yesterday

marko

7,65142338

answered yesterday

marko

7,65142338

answered yesterday

marko

7,65142338

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

add a comment |

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

"Every single addition will result in a memory allocation" -- yes, but note that Java virtual machines are usually highly optimized around the fact that most Java programs perform a lot of memory allocations. Java uses extremely fast allocation techniques with a trade-off of needing more complex reclamation of memory along with the hope that the latter won't be needed if the allocation pattern is simple enough or if the program is short-lived. The problem here is small and self-contained, so the GC should be able to deal with it quickly, too. Cache locality is almost certainly the key here.
– Jules
16 hours ago

Boxing to Character does not necessarily lead to an allocation, as all values in the ASCII range are cached. But the HashMap itself creates an entry instance for every association.
– Holger
9 hours ago

add a comment |

up vote
10
down vote

O(n²) is only the worst case time complexity of the second approach.

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

edited yesterday

answered yesterday

user202729

1,0613719

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

add a comment |

up vote
10
down vote

O(n²) is only the worst case time complexity of the second approach.

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

edited yesterday

answered yesterday

user202729

1,0613719

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

add a comment |

up vote
10
down vote

O(n²) is only the worst case time complexity of the second approach.

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

edited yesterday

answered yesterday

user202729

1,0613719

O(n²) is only the worst case time complexity of the second approach.

However:

For strings with each character chosen independently, uniformly from {a,b,c,...,z} ^[1], the expected time complexity should be O(n).

^[1]: In the original leetcode challenge, it is said that

You may assume the string contain only lowercase letters.

However, that is not mentioned in the question.

edited yesterday

answered yesterday

user202729

1,0613719

edited yesterday

answered yesterday

user202729

1,0613719

answered yesterday

user202729

1,0613719

answered yesterday

user202729

1,0613719

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

add a comment |

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

The problem with this analysis as far as I can see is that you limit the alphabet size to 26 characters. If we don't do this, I would assume that the length of the alphabet in comparison to the length of the string also influences the complexity.
– Voo
yesterday

@voo In the leetcode example it's true. (although, unfortunately, it is not mentioned in the question)
– user202729
yesterday

For all practical purposes the alphabet is probably going to be <100 absolutely and if the question even specifies it, even better. I just overlooked your set specification on first glance and was really confused how the statement could hold for arbitrary large character sets (although char is limited to 65k anyhow) and played around with it a bit.
– Voo
yesterday

add a comment |

up vote
3
down vote

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

answered yesterday

yaccob

59359

add a comment |

up vote
3
down vote

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

answered yesterday

yaccob

59359

add a comment |

up vote
3
down vote

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

answered yesterday

yaccob

59359

Karol already provided a good explanation for your special case. I want to add a general remark regarding the big O notation for time complexity.

In general this time complexity doesn't tell you too much about the actual performance. It just gives you an idea of the number of iterations needed by a particular algorithm.

Let me put it like this: if you execute a huge amount of fast iterations this can still be faster than executing very few extremely slow iterations.

answered yesterday

yaccob

59359

answered yesterday

yaccob

59359

answered yesterday

yaccob

59359

answered yesterday

yaccob

59359

add a comment |

up vote
0
down vote

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>

#include <string_view>

int first_unique_char(char s, int s_len) noexcept {

    std::map<char, int> char_hash;

    int res = -1;

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        auto r = char_hash.find(c);

        if (r == char_hash.end())

            char_hash.insert(std::pair<char, int>(c,1));

        else {

            int new_val = r->second + 1;

            char_hash.erase(c);

            char_hash.insert(std::pair<char, int>(c, new_val));

        }

    }

    for (int i = 0; i < s_len; i++)

        if (char_hash.find(s[i])->second == 1) {

            res = i;

            break;

        }

    return res;

}

int first_unique_char2(char s, int s_len) noexcept {

    int res = -1;

    std::string_view str = std::string_view(s, s_len);

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        if (str.find_first_of(c) == str.find_last_of(c)) {

            res = i;

            break;

        }

    }

    return res;

}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())

        char_hash.insert(std::pair<char, int>(c,1));

    else {

        int new_val = r->second + 1;

        char_hash.erase(c);

        char_hash.insert(std::pair<char, int>(c, new_val));

    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.

edited yesterday

answered yesterday

MCCCS

3761727

2

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

add a comment |

up vote
0
down vote

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>

#include <string_view>

int first_unique_char(char s, int s_len) noexcept {

    std::map<char, int> char_hash;

    int res = -1;

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        auto r = char_hash.find(c);

        if (r == char_hash.end())

            char_hash.insert(std::pair<char, int>(c,1));

        else {

            int new_val = r->second + 1;

            char_hash.erase(c);

            char_hash.insert(std::pair<char, int>(c, new_val));

        }

    }

    for (int i = 0; i < s_len; i++)

        if (char_hash.find(s[i])->second == 1) {

            res = i;

            break;

        }

    return res;

}

int first_unique_char2(char s, int s_len) noexcept {

    int res = -1;

    std::string_view str = std::string_view(s, s_len);

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        if (str.find_first_of(c) == str.find_last_of(c)) {

            res = i;

            break;

        }

    }

    return res;

}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())

        char_hash.insert(std::pair<char, int>(c,1));

    else {

        int new_val = r->second + 1;

        char_hash.erase(c);

        char_hash.insert(std::pair<char, int>(c, new_val));

    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.

edited yesterday

answered yesterday

MCCCS

3761727

2

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

add a comment |

up vote
0
down vote

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>

#include <string_view>

int first_unique_char(char s, int s_len) noexcept {

    std::map<char, int> char_hash;

    int res = -1;

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        auto r = char_hash.find(c);

        if (r == char_hash.end())

            char_hash.insert(std::pair<char, int>(c,1));

        else {

            int new_val = r->second + 1;

            char_hash.erase(c);

            char_hash.insert(std::pair<char, int>(c, new_val));

        }

    }

    for (int i = 0; i < s_len; i++)

        if (char_hash.find(s[i])->second == 1) {

            res = i;

            break;

        }

    return res;

}

int first_unique_char2(char s, int s_len) noexcept {

    int res = -1;

    std::string_view str = std::string_view(s, s_len);

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        if (str.find_first_of(c) == str.find_last_of(c)) {

            res = i;

            break;

        }

    }

    return res;

}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())

        char_hash.insert(std::pair<char, int>(c,1));

    else {

        int new_val = r->second + 1;

        char_hash.erase(c);

        char_hash.insert(std::pair<char, int>(c, new_val));

    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.

edited yesterday

answered yesterday

MCCCS

3761727

I've ported the functions to C++(17) to see if the difference was caused by algorithm complexity or Java.

#include <map>

#include <string_view>

int first_unique_char(char s, int s_len) noexcept {

    std::map<char, int> char_hash;

    int res = -1;

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        auto r = char_hash.find(c);

        if (r == char_hash.end())

            char_hash.insert(std::pair<char, int>(c,1));

        else {

            int new_val = r->second + 1;

            char_hash.erase(c);

            char_hash.insert(std::pair<char, int>(c, new_val));

        }

    }

    for (int i = 0; i < s_len; i++)

        if (char_hash.find(s[i])->second == 1) {

            res = i;

            break;

        }

    return res;

}

int first_unique_char2(char s, int s_len) noexcept {

    int res = -1;

    std::string_view str = std::string_view(s, s_len);

    for (int i = 0; i < s_len; i++) {

        char c = s[i];

        if (str.find_first_of(c) == str.find_last_of(c)) {

            res = i;

            break;

        }

    }

    return res;

}

The result was:

The second one is ~30% faster for leetcode.

Later, I noticed that

    if (r == char_hash.end())

        char_hash.insert(std::pair<char, int>(c,1));

    else {

        int new_val = r->second + 1;

        char_hash.erase(c);

        char_hash.insert(std::pair<char, int>(c, new_val));

    }

could be optimized to

    char_hash.try_emplace(c, 1);

Which also confirms that complexity is not only the only thing. There's "input length", which other answers have covered and lastly, I noticed that

Implementation also makes a difference. Longer code hides optimization opportunities.

edited yesterday

answered yesterday

MCCCS

3761727

edited yesterday

answered yesterday

MCCCS

3761727

answered yesterday

MCCCS

3761727

answered yesterday

MCCCS

3761727

2

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

add a comment |

2

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

This isn't the same thing as the equivalent of HashMap would rather be std::unordered_map. std::map would be a TreeMap AFAIK.
– Moira
yesterday

^, std::map performance is poor compared to umap for these things.
– Sombrero Chicken
yesterday

add a comment |

up vote
0
down vote

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

answered 9 hours ago

Damon

50.2k1496152

add a comment |

up vote
0
down vote

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

answered 9 hours ago

Damon

50.2k1496152

add a comment |

up vote
0
down vote

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

answered 9 hours ago

Damon

50.2k1496152

Every operation thus involves at least two indirections, plus some calculations. That, all in all, is painfully expensive compared to just iterating over a small array a couple of times.

answered 9 hours ago

Damon

50.2k1496152

answered 9 hours ago

Damon

50.2k1496152

answered 9 hours ago

Damon

50.2k1496152

answered 9 hours ago

Damon

50.2k1496152

add a comment |

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu