Rank: 5144 based on 5 downloads (last 30 days) and 1 file submitted
photo

Manel Soria

E-mail

Personal Profile:
Professional Interests:

 

Watch this Author's files

 

Files Posted by Manel
  • 1 - 1 of
  • 1
Updated   File Tags Downloads
(last 30 days) 		Comments Rating
05 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria demo, data import, statistics 5 5
Comments and Ratings by Manel View all
  • 1 - 5 of
  • 9
Updated File Comments Rating
08 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria

First, thanks for your comment, I see that strmatch isn't a good choice at all.
It seems there is a small mistake in your code, should it be c{k} = sprintf('%d', k); in the second line ?
My timings are different:
tic; for i=1:100:n; f= quickfindstr(c{i}, c); end; toc
% 4.697042
tic; for i=1:100:n; f= find(strcmp(c{i}, c)); end; toc
% 6.770262
tic; for i=1:100:n; f= strmatch(c{i}, c, 'exact'); end; toc
% 48.737699
What Matlab version are you using ? On what machine ? I'm running 2011b on a late 2009 Imac
To conclude, I tested the following
>> tic; for i=1:100; f= find(strcmp(c{1}, c)); end; toc
Elapsed time is 0.385195 seconds.
>> tic; for i=1:100; f= find(strcmp(c{150000}, c)); end; toc
Elapsed time is 0.469383 seconds.
Thus, strcmp isn't just a linear search algorithm as I expected. I wonder how is it working
06 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria

Thanks for the comment !
Can you please post how you do it and the time it takes ?
In any case, a sequential strcmp will be a O(N) operation and for large sets this method, O(logN) should be faster
28 Feb 2013 X Steam, Thermodynamic properties of water and steam. Water properties A complete IAPWS IF-97 standard. Author: Magnus Holmgren

Excellent !!
23 Jan 2013 Making Surface Plots From Scatter Data How to turn a collection of XYZ triplets into a surface plot. Author: Zain Mecklai

Thanks !
13 Jan 2013 unique with tolerance Similar to Unique, gives unique element within a tolerance. Author: Siyi Deng

After a long execution of another script that calls many times uniquetol, it crashed:

Index exceeds matrix dimensions (line 33):
z = y(isTol,:);

This happened twice and I don't see what can be the origin as I can't have the data that caused the crash. If it is an error of uniquetol I don't see it

Any suggestion ?
Comments and Ratings on Manel's Files View all
  • 1 - 5 of
  • 5
Updated File Comment by Comments Rating
15 Apr 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria Simon, Jan

@Manel: Thanks for fixing the typo. I've meaured the timings on a Core2Duo/2009a/64/Win7 system.

strcmp(c{150000}, c) needs longer than for c{1}, because the contents of c{1} is shorter. There are only 9 strings in c, which have one character only, while for C{150000}='150000' there are a lot of strings with size 6, such that an explicit comparison is started. In addition, a comparison of a shorter string is faster than of a longer string, because less bytes have to be processed.
08 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria Soria, Manel

First, thanks for your comment, I see that strmatch isn't a good choice at all.
It seems there is a small mistake in your code, should it be c{k} = sprintf('%d', k); in the second line ?
My timings are different:
tic; for i=1:100:n; f= quickfindstr(c{i}, c); end; toc
% 4.697042
tic; for i=1:100:n; f= find(strcmp(c{i}, c)); end; toc
% 6.770262
tic; for i=1:100:n; f= strmatch(c{i}, c, 'exact'); end; toc
% 48.737699
What Matlab version are you using ? On what machine ? I'm running 2011b on a late 2009 Imac
To conclude, I tested the following
>> tic; for i=1:100; f= find(strcmp(c{1}, c)); end; toc
Elapsed time is 0.385195 seconds.
>> tic; for i=1:100; f= find(strcmp(c{150000}, c)); end; toc
Elapsed time is 0.469383 seconds.
Thus, strcmp isn't just a linear search algorithm as I expected. I wonder how is it working
07 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria Simon, Jan

Some tests under Matlab 2009a/64/Win7:

n = 150000; c = cell(1, n);
for k = 1:n; c = sprintf('%d', k); end;
c = sort(c);
tic; for i=1:100:n; f= quickfindstr(c{i}, c); end; toc
% 6.043004 seconds
tic; for i=1:100:length(c); f= find(strcmp(c{i}, c)); end; toc
% 7.903860 seconds
tic; for i=1:100:length(c); f= strmatch(c{i}, c, 'exact'); end; toc
% 56.037904 seconds

For n=15'000 the timings are:
quickfindstr: 0.437317 seconds
find(strcmp): 0.054181 seconds
strmatch: 0.417264 seconds

This shows, that for 150'000 strings you methods beats find(strcmp).

06 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria Soria, Manel

Thanks for the comment !
Can you please post how you do it and the time it takes ?
In any case, a sequential strcmp will be a O(N) operation and for large sets this method, O(logN) should be faster
06 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria Simon, Jan

The comparison with the very slow STRMATCH is not fair. On one hand this command is deprecated now, on the other FIND(STRCMP) is much faster.
Top Tags Applied by Manel
  • 1 - 3 of
  • 3
data import, demo, statistics
Files Tagged by Manel
  • 1 - 1 of
  • 1
Updated   File Tags Downloads
(last 30 days) 		Comments Rating
05 Mar 2013 quickfindstr Finds the index of an element in a SORTED list of strings in O(log(N)) time Author: Manel Soria demo, data import, statistics 5 5

Contact us