1. Looking for the best "JOIN"
- Posted by euman at bellsouth.net Oct 21, 2001
- 439 views
Im looking for the best JOIN method. Heres what I have: {"str1","str2","str3"} Heres what I want: "str1str2str3" No slow ideas please>>>> Euman euman at bellsouth.net
2. Looking for the best "JOIN"
- Posted by euman at bellsouth.net Oct 21, 2001
- 410 views
BTW, anyother way to do what I wanted other than this is what I would like to see.. for i = 1 to length(ipath) do path &= ipath[i][1..length(ipath[i])] end for Euman euman at bellsouth.net
3. Re: Looking for the best "JOIN"
- Posted by Derek Parnell <ddparnell at bigpond.com> Oct 22, 2001
- 392 views
----- Original Message ----- From: <euman at bellsouth.net> To: "EUforum" <EUforum at topica.com> Subject: Looking for the best "JOIN" > > Im looking for the best JOIN method. > > Heres what I have: {"str1","str2","str3"} > > Heres what I want: "str1str2str3" > > No slow ideas please>>>> Okay, I'll bite. --------------------- global function joinStrings(sequence s) integer l,a,b sequence t if length(s) = 0 then return s end if l = 0 for i = 1 to length(s) do l += length(s[i]) end for t = repeat(0, l) a = 1 for i = 1 to length(s) do b = a + length(s[i]) - 1 t[a..b] = s[i] a = b + 1 end for return t end function -- Test code -- constant words = {"abc","defghi","jklmnopqr","","st","u","vwxyz"} atom e sequence k integer x x = 0 e = time() + 10 while e >= time() do x += 1 k =joinStrings(words) end while printf(1, "%d interations in 10 seconds\n", x) --------------------- Derek
4. Re: Looking for the best "JOIN"
- Posted by euphoria at carlw.legend.uk.com Oct 22, 2001
- 382 views
Euman wrote: > Im looking for the best JOIN method. > > Heres what I have: {"str1","str2","str3"} > > Heres what I want: "str1str2str3" function join(sequence s) -- this is the way most people would do it sequence j if not length(s) then return s end if j = {} for i = 1 to length(s) j &= s[i] end for return j end function ...or...: function join2(sequence s) -- this shouldn't be any faster but who knows? sequence j integer mid, len len = length(s) if not len then return s elsif len = 1 then return s[1] elsif len = 2 then return s[1]&s[2] end if mid = floor(len/2) return join2(s[1..mid])&join2(s[mid+1..len]) end function Carl
6. Re: Looking for the best "JOIN"
- Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Oct 22, 2001
- 393 views
Derek, simple concatenation seems to be marginally faster, I got 214,361 : 193,488. Try it. jiri global function joinStrings(sequence s) integer l,a,b sequence t if length(s) = 0 then return s end if l = 0 for i = 1 to length(s) do l += length(s[i]) end for t = repeat(0, l) a = 1 for i = 1 to length(s) do b = a + length(s[i]) - 1 t[a..b] = s[i] a = b + 1 end for return t end function function join(sequence s) sequence r r = {} for i = 1 to length(s) do r &= s[i] end for return r end function -- Test code -- constant words = {"abc","defghi","jklmnopqr","","st","u","vwxyz"} puts(1, join(words) & "\n") puts(1, joinStrings(words) & "\n") atom e sequence k integer x x = 0 e = time() + 10 while e >= time() do x += 1 k =join(words) end while printf(1, "%d interations in 10 seconds\n", x) x = 0 e = time() + 10 while e >= time() do x += 1 k =joinStrings(words) end while printf(1, "%d interations in 10 seconds\n", x)
7. Re: Looking for the best "JOIN"
- Posted by Derek Parnell <ddparnell at bigpond.com> Oct 22, 2001
- 399 views
I found this too. I got about 285,000 vs 270,000. I suspect that Euphoria has better garbage collection when using the '&' operator. ----- Original Message ----- From: "Jiri Babor" <jbabor at PARADISE.NET.NZ> To: "EUforum" <EUforum at topica.com> Subject: Re: Looking for the best "JOIN" > > Derek, > > simple concatenation seems to be marginally faster, I got 214,361 : > 193,488. > Try it. > > jiri > > > global function joinStrings(sequence s) > integer l,a,b > sequence t > > if length(s) = 0 then > return s > end if > > l = 0 > for i = 1 to length(s) do > l += length(s[i]) > end for > > t = repeat(0, l) > > a = 1 > for i = 1 to length(s) do > b = a + length(s[i]) - 1 > t[a..b] = s[i] > a = b + 1 > end for > > return t > end function > > function join(sequence s) > sequence r > > r = {} > for i = 1 to length(s) do > r &= s[i] > end for > return r > end function > > -- Test code -- > constant words = {"abc","defghi","jklmnopqr","","st","u","vwxyz"} > puts(1, join(words) & "\n") > puts(1, joinStrings(words) & "\n") > > atom e > sequence k > integer x > > x = 0 > e = time() + 10 > while e >= time() do > x += 1 > k =join(words) > end while > printf(1, "%d interations in 10 seconds\n", x) > > x = 0 > e = time() + 10 > while e >= time() do > x += 1 > k =joinStrings(words) > end while > printf(1, "%d interations in 10 seconds\n", x) > > >
8. Re: Looking for the best "JOIN"
- Posted by Derek Parnell <ddparnell at bigpond.com> Oct 22, 2001
- 423 views
Unsaid in Euman request, but assumed by others is the desire to find a method of joining an abitary number of strings. The exact number would not be known until run-time. If we were to take Euman's request a face value the answer might be ... function join() return "str1str2str3" end function because that is literally what he asked for, 'Heres what I want: "str1str2str3"'. ----- Original Message ----- From: "Andy Drummond" <kestrelandy at xalt.co.uk> To: "EUforum" <EUforum at topica.com> Sent: Monday, October 22, 2001 10:54 PM Subject: RE: Looking for the best "JOIN" > > Have I missed something? > Surely this is built in to Euphoria as a fundamental? > > sequence x > > x = "abc"&"def"&"ghijk" > > ... and d then = "abcdefghijk" > > I just tried it and it does ... so? > > Andy > > > euman at bellsouth.net wrote: > > Im looking for the best JOIN method. > > > > Heres what I have: {"str1","str2","str3"} > > > > Heres what I want: "str1str2str3" > > > > No slow ideas please>>>> > > > > Euman > > euman at bellsouth.net > > > > > >
9. Re: Looking for the best "JOIN"
- Posted by Derek Parnell <ddparnell at bigpond.com> Oct 22, 2001
- 400 views
Hi Andy, Sorry about my offhanded comment before. Your function, I believe, is the most obvious. However, I've learnt that the most obvious algorithm is not always the fastest one. Here is the reasoning behind my first effort... The obvious algorithm, I guessed, does this sort of thing internally... > function join (sequence strings) > sequence result > result = "" > for i=1 to length(strings) -- Allocate some RAM big enough to hold the current -- length of result plus the length of strings[i] -- Copy the values in result to the new area -- Copy the values in strings[i] to the new area -- Return the old area (aka old results) to the system > result = result & strings[i] > end for > return result > end function Thus for each element in strings it would do 1 Allocate, 2 Copys, and one deallocate. Also, the copys would be increasing in size for each iteration. Meaning that some values would be copied multiple times. I wrote my function thinking that if I just did the one allocation, regardless of how many elements in 'strings' then only copy each value once it would be faster. This would mean I'd have to do a loop through 'strings' to calc the total length, then loop through again to copy each of the values. However, it turns out that the overheads in running two loops through the elements in 'strings' is more than the allocate/copy/copy/deallocate cycle. (I guess). ---- Derek.
10. Re: Looking for the best "JOIN"
- Posted by Igor Kachan <kinz at peterlink.ru> Oct 22, 2001
- 418 views
Hi Euman, ---------- > Im looking for the best JOIN method. > > Heres what I have: {"str1","str2","str3"} > > Heres what I want: "str1str2str3" > > No slow ideas please>>>> Your question has analogy with my question from the Threaded Euphoria thread, remember ? {java & browser & windows & applet} system Just analogy which seems to be amusing, and it seems to be similar with string execution from my favourite Basic 02 of Soviet Iskra 226 machine. Just analogies, which may be useful for the list authors. Good luck with this. Regards, Igor Kachan kinz at peterlink.ru
11. Re: Looking for the best "JOIN"
- Posted by euman at bellsouth.net Oct 23, 2001
- 405 views
I really never intended for this to be a war to see who's routine was the best but it sure has been fun sitting back watching you all duke it out...hehe Now that we have the fastest method, what the hek do we do with it? just picking! Thanks JB, DP, CB, RF, IK, AD, RS, CW and ROB.... Euman euman at bellsouth.net
12. Re: Looking for the best "JOIN"
- Posted by rolf.schroeder at desy.de Oct 23, 2001
- 384 views
That's funny, I did'nt know that I found Jiri's fast 'join()' in advance! Have a nice day, Rolf
13. Re: Looking for the best "JOIN"
- Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Oct 24, 2001
- 404 views
You can have it, Rolf, since you appear so desperate. Frame it! I only wish you lot stopped using my name in vain... jiri ----- Original Message ----- From: <rolf.schroeder at desy.de> To: "EUforum" <EUforum at topica.com> Subject: Re: Looking for the best "JOIN" > > That's funny, > > I did'nt know that I found Jiri's fast 'join()' in advance! > > Have a nice day, Rolf > > >
14. Re: Looking for the best "JOIN"
- Posted by rolf.schroeder at desy.de Oct 24, 2001
- 389 views
Jiri Babor wrote: > You can have it, Rolf, since you appear so desperate. > Frame it! > > I only wish you lot stopped using my name in vain... > > jiri Hi Jiri, I'm waiting vor ALL responses to my mail just to 'join' them with the quickest routine . . . Have a nice day, Rolf
15. Re: Looking for the best "JOIN"
- Posted by Igor Kachan <kinz at peterlink.ru> Oct 24, 2001
- 408 views
16. Re: Looking for the best "JOIN"
- Posted by rforno at tutopia.com Oct 24, 2001
- 389 views
Yes, my routine takes into account an empty input sequence, not explicitly, but it does. Try it. In this case, it is a bit slower, but I think it doesn't matter... ----- Original Message ----- From: <bensler at mail.com> To: "EUforum" <EUforum at topica.com> Subject: RE: Looking for the best "JOIN" > > First of all, > > Igor, the entire reason I attempted to improve on the JOIN algorithm, was because I thought the same thing as you :), that it isn't necessary to have a return sequence, when you can utilize the first element of the input sequence. But this proves to be MUCH slower because EU has to shuffle the data in the sequence too much(this is my assumption anyways). > > Rforno, your version doesn't take into account empty sequences for input. > > Now, I made a NEW bench test, which should prove to be much more accurate. It's attached. > > Here are my results. > (For EXE.EXE only) > > 10000 iterations of operations on 10000 random sequences using 4 different versions of join() > (Total of 4000000 iterations) > > my version : 139180 iterations per second > Derek's : 142229 > Jiri's : 133288 > Igor's : 71904 > > The results are fairly close in this test but I found that on the whole, Derek's routine was much more consistent, and always greater than the others. > > Using not quite as extreme of a test, the results are similar from a DOS box. I didn't test pure DOS. > > Also, I was able to improve Derek's routine by about 8%. > He originally had it to test for an empty input sequence at the start of the routine. > This means that his routine requires a conditional jump every time the input sequence is NOT empty. > I just reversed it, so it only branches when the input sequence IS empty. > > There ya go Euman :) > Derek's routine is fastest(with minor modification) > > function joinStrings(sequence s) > integer l,a,b > sequence t > > if length(s) then > l=0 > for i = 1 to length(s) do > l+=length(s[i]) > end for > > t =repeat(0,l) > a=1 > for i = 1 to length(s) do > b = a + length(s[i]) - 1 > t[a..b] = s[i] > a = b+1 > end for > > return t > end if > return s > end function > > Chris > -- > > >