I have a list of strings and I have to find whether a string is present in that list or not. I wanted to use the logic in low latency pricing engine so I wanted to have real fast logic for it. I thought of having these strings stored in map as keys and then could use find() or count() function for the same. Can anyone suggest any other more efficient logic for the same?
Add a comment
|
2 Answers
Probably std::unordered_set is an appropriate choice for your needs. You would then use find() to check if a string is present or not. Something like the example code here:
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset{ "red", "green", "blue" };
std::cout << "color? ";
std::string input;
std::cin >> input;
auto pos = myset.find(input);
if (pos != myset.end())
std::cout << *pos << " is in myset\n";
else
std::cout << "not found in myset\n";
}
To understand how std::unordered_set works, please see hash set.
8 Comments
Bhupesh Pant
yes Ali, my code is a c++ code. I have just added the pseudo code for the logic.
Bhupesh Pant
That 100% answers my question. I also found out that my strfind() way of doing is also not efficient as well... since its slower traditional C way of string manipulation..
Ali
@BhupeshPant OK, I am glad it helped. I have added a little example code.
Bhupesh Pant
what would be you suggestion in case we have integers without any duplicate entry? Data structure wise I would say normal binary tree would do. but which stl class should be used? I am completely new to STL world so I am sorry if I am asking some very basic questions.
Ali
@BhupeshPant It also depends on how you use it. Either
unordered_set<int> or a sorted vector<int> with lower_bound(). If you want to a tree, then set<int>, although that is probably the slowest wrt lookup. |
One more way I just now thought of is,
Put the list of string in single semicolon separated string and then use strfind.
e.g.
List of string, <ABC,DEF,GHI,JKL,MNO,PQRS,LMNOPQR, STUVW,XY,Z>
l_czEIDHolder = “ABC;DEF;GHI;JKL;MNO;PQRS;LMNOPQR; STUVW;XY;Z”
if string_to_search = “PQRS”
make string_to_search = string_to_search +”;”
strfind(czEIDHolder, string_to_search) OR
string::find(czEIDHolder, string_to_search)
5 Comments
IInspectable
-1 Convoluted solution. That fails if your search string contains your proposed delimiter (semicolon). Plus, since you were asking for fast, slow is not an answer (O(1) vs. O(n)).
Bhupesh Pant
For that I am sure that It will not contains that delimiter. I will only take your second point for (-1).. Thanks for your reply.
IInspectable
Also fails, if your search string matches the tail end (but not the entire string). This is not a solution.
Bhupesh Pant
Accepted all your point.But all your points come into consideration after the fact that I will choose this way. C is very bad in handling string. All the string functions that C offers are not at all considered as efficient. Thats why we have std::string to effectively handle string operations as other language do. So choice of having he above solution is already ruled out and if you have read my main intention, is to achieve efficiency. Thanks for your findings. Thanks a lot.
IInspectable
std::string is implemented in terms of the C string handling functions. C++ is, if anything, less efficient. You need to get familiar with a profiler. Even if it were faster this answer proposes a slow algorithm. Lookup with an unordered_set is amortized constant time on average, worst case linear time. Your lookup is always linear time. Of course this can be further optimized by not using a string as an ID. String comparisons are inherently slow, when compared to integer comparisons.