Forum: Ruby Q: most efficient way to remove duplicate spaces in a string?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Mark W. (Guest)
on 2009-01-09 20:25
(Received via mailing list)
I don't usually worry too much about efficiency unless runtime
performance becomes an issue so I use a_string.split.join(' ') to
remove extra spaces because the code is short and readable.

This is certainly inefficient. What is the fastest idiom for this
operation?

Thanks,
Mark
Chris S. (Guest)
on 2009-01-09 20:30
(Received via mailing list)
On Jan 9, 11:20 am, Mark  Watson <removed_email_address@domain.invalid> wrote:
> I don't usually worry too much about efficiency unless runtime
> performance becomes an issue so I use a_string.split.join(' ') to
> remove extra spaces because the code is short and readable.
>
> This is certainly inefficient. What is the fastest idiom for this
> operation?
>
> Thanks,
> Mark

Haven't benchmarked it, but this sounds like a case for regular
expressions.

  a_string.gsub!(/ +/, ' ')

HTH,
Chris
pat eyler (Guest)
on 2009-01-09 20:48
(Received via mailing list)
On Fri, Jan 9, 2009 at 11:29 AM, Chris S. <removed_email_address@domain.invalid> 
wrote:
>
> Haven't benchmarked it,


require 'benchmark'

n = 1_000_000

Benchmark.bm(10) do |x|
  x.report("gsub") { n.times do
      "This     is  a test   string.".gsub(/ +/, ' ')
    end
  }
  x.report("gsub!") { n.times do
      "This     is  a test   string.".gsub!(/ +/, ' ')
    end
  }
  x.report("split.join") { n.times do
      "This     is  a test   string.".split.join(' ')
    end
  }
end


                user     system      total        real
gsub        6.310000   0.080000   6.390000 (  7.135028)
gsub!       6.300000   0.070000   6.370000 (  7.064374)
split.join  3.940000   0.070000   4.010000 (  4.160529)


or, with bmbm

pate@pate:~/scratch$ ./stringcleanup.rb
Rehearsal ----------------------------------------------
gsub         6.290000   0.170000   6.460000 (  7.956565)
gsub!        6.370000   0.170000   6.540000 (  8.128309)
split.join   3.990000   0.080000   4.070000 (  4.832332)
------------------------------------ total: 17.070000sec

                 user     system      total        real
gsub         6.220000   0.130000   6.350000 (  7.613061)
gsub!        6.390000   0.080000   6.470000 (  8.284855)
split.join   3.970000   0.120000   4.090000 (  5.684406)


Please, benchmark first.  It's not that hard:

http://on-ruby.blogspot.com/2008/12/benchmarking-m...
Patrick D. (Guest)
on 2009-01-09 20:58
(Received via mailing list)
On Fri, Jan 9, 2009 at 1:24 PM, Mark W. <removed_email_address@domain.invalid>
wrote:

> I don't usually worry too much about efficiency unless runtime
> performance becomes an issue so I use a_string.split.join(' ') to
> remove extra spaces because the code is short and readable.
>
> This is certainly inefficient. What is the fastest idiom for this
> operation?
>
I was looking at the docs the other day and stumbled across
String#squeeze.
You might try benchmarking that.

--wpd
Robert K. (Guest)
on 2009-01-09 21:01
(Received via mailing list)
On 09.01.2009 19:47, pat eyler wrote:
>>> Mark
>     end
>   }
>   x.report("gsub!") { n.times do
>       "This     is  a test   string.".gsub!(/ +/, ' ')
>     end
>   }
>   x.report("split.join") { n.times do
>       "This     is  a test   string.".split.join(' ')
>     end
>   }
> end

Note that these behave differently.  A more appropriate comparison would
be to use /\s+/ as regular expression for gsub!.

Interesting figures btw.  I would have guessed that gsub! is fastest -
live and learn.

Kind regards

  robert
Craig D. (Guest)
on 2009-01-09 21:02
(Received via mailing list)
I was just doing that. :-)

require 'benchmark'

n = 1_000_000

Benchmark.bm(10) do |x|
 x.report("gsub") { n.times do
     "This     is  a test   string.".gsub(/ +/, ' ')
   end
 }
 x.report("gsub!") { n.times do
     "This     is  a test   string.".gsub!(/ +/, ' ')
   end
 }
 x.report("split.join") { n.times do
     "This     is  a test   string.".split.join(' ')
   end
 }
 x.report("squeeze.strip") { n.times do
     "This     is  a test   string.".squeeze(' ').strip
   end
 }
end

                user     system      total        real
gsub        4.470000   0.040000   4.510000 (  4.578173)
gsub!       4.390000   0.020000   4.410000 (  4.468695)
split.join  3.500000   0.020000   3.520000 (  3.556669)
squeeze.strip  1.980000   0.010000   1.990000 (  2.003622)

Regards,
Craig
Tim G. (Guest)
on 2009-01-09 21:55
(Received via mailing list)
Craig D. wrote:

>      "This     is  a test   string.".gsub(/ +/, ' ')
>  x.report("squeeze.strip") { n.times do
>
> Regards,
> Craig


The ruby version plays a big role in squeeze.strip, as it's much slower
than split.join with an older version on one of my systems.

Also, try the following variations and see the slight speed increase for
gsub/gsub! (small increase, but interesting to note):

I.e.:

n = 1_000_000

string = "This   is  a test    string."

Benchmark.bm(10) do |x|
 x.report("gsub") { n.times do
        string.gsub(/ +/, ' ')
 end
 }
 x.report("gsub #2") { n.times do
        string.gsub(/ {2,}/, ' ')
 end
 }
 x.report("gsub #3") { n.times do
        string.gsub(/  +/, ' ')
 end
 }

old ruby 1.8.1 on one system:

                user     system      total        real
gsub        9.090000   0.000000   9.090000 (  9.111154)
gsub #2     8.600000   0.000000   8.600000 (  8.643407)
gsub #3     7.560000   0.000000   7.560000 (  7.579185)
gsub!       8.060000   0.000000   8.060000 (  8.061861)
gsub! #2    8.110000   0.000000   8.110000 (  8.115992)
split.join  4.730000   0.000000   4.730000 (  4.733248)
squeeze.strip  6.140000   0.000000   6.140000 (  6.132690)

Ruby 1.8.7 on another system:

                user     system      total        real
gsub        3.660000   0.000000   3.660000 (  3.663209)
gsub #2     3.450000   0.000000   3.450000 (  3.455171)
gsub #3     3.070000   0.000000   3.070000 (  3.065939)
gsub!       3.500000   0.000000   3.500000 (  3.517176)
gsub! #2    3.510000   0.000000   3.510000 (  3.506881)
split.join  2.550000   0.000000   2.550000 (  2.560460)
squeeze.strip  1.580000   0.000000   1.580000 (  1.588717)

I'll see if I can get a chance to upgrade ruby on the older system to
see the results.
Mark W. (Guest)
on 2009-01-09 22:25
(Received via mailing list)
On Jan 9, 11:20 am, Mark  Watson <removed_email_address@domain.invalid> wrote:
> I don't usually worry too much about efficiency unless runtime
> performance becomes an issue so I use a_string.split.join(' ') to
> remove extra spaces because the code is short and readable.
>
> This is certainly inefficient. What is the fastest idiom for this
> operation?
>
> Thanks,
> Mark

Thanks to everyone who responded!

Best regards,
Mark
Clifford H. (Guest)
on 2009-01-10 03:21
(Received via mailing list)
Robert K. wrote:
> Note that these behave differently...
> Interesting figures btw.  I would have guessed that gsub! is fastest -
> live and learn

It still might be - the benchmark doesn't run long enough to
compare the GC overhead of making dozens of little strings
that get used once each.
pat eyler (Guest)
on 2009-01-10 21:00
(Received via mailing list)
On Fri, Jan 9, 2009 at 6:20 PM, Clifford H. 
<removed_email_address@domain.invalid>
wrote:
>
Is this better?

#!/usr/bin/ruby

require 'benchmark'

n = 1_000_000

Benchmark.bm(10) do |x|
  x.report("gsub") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub(/ +/, ' ')
    end
  }
  x.report("gsub!") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub!(/ +/, ' ')
    end
  }
  x.report("split.join") { n.times do
      a_string = "This     is  a test   string."
      a_string.split.join(' ')
    end
  }
  x.report("squeeze.strip") { n.times do
      a_string = "This     is  a test   string."
      a_string.squeeze(' ').strip
    end
  }
end



$ ./stringcleanup.rb
                user     system      total        real
gsub        7.170000   0.140000   7.310000 ( 11.034766)
gsub!       6.900000   0.150000   7.050000 ( 14.113575)
split.join  4.450000   0.110000   4.560000 (  7.518476)
squeeze.strip  3.180000   0.100000   3.280000 (  4.943830)
Tim G. (Guest)
on 2009-01-10 22:16
(Received via mailing list)
pat eyler wrote:

>> that get used once each.
>
>   }
> end
>
For gsub/gsub!, instead of replacing one or more white space with a
white space, speed it up by replacing two or more white space with a
white space.  This saves unneeded processing by not replacing single
white space.  I.e., instead of gsub(/ +/, ' '), try gsub(/  +/, ' ') or
gsub(/ {2,}/, ' ') and benchmark them (they should be faster).  Of
course, it's still not going to be as fast as split.join or
squeeze.strip (at least depending on the version of ruby used, as older
ruby versions may put squeeze.strip markedly slower than split.join.
pat eyler (Guest)
on 2009-01-10 22:47
(Received via mailing list)
On Sat, Jan 10, 2009 at 1:14 PM, Tim G. <removed_email_address@domain.invalid> 
wrote:
> For gsub/gsub!, instead of replacing one or more white space with a
> white space, speed it up by replacing two or more white space with a
> white space.  This saves unneeded processing by not replacing single
> white space.  I.e., instead of gsub(/ +/, ' '), try gsub(/  +/, ' ') or
> gsub(/ {2,}/, ' ') and benchmark them (they should be faster).  Of
> course, it's still not going to be as fast as split.join or
> squeeze.strip (at least depending on the version of ruby used, as older
> ruby versions may put squeeze.strip markedly slower than split.join.

#!/usr/bin/ruby

require 'benchmark'

n = 1_000_000

Benchmark.bm(15) do |x|
  x.report("gsub") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub(/ +/, ' ')
    end
  }
  x.report("gsub!") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub!(/ +/, ' ')
    end
  }
  x.report("gsub2") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub(/ {2,}/, ' ')
    end
  }
  x.report("gsub!2") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub!(/ {2,}/, ' ')
    end
  }
  x.report("gsub s") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub(/\s+/, ' ')
    end
  }
  x.report("gsub! s") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub!(/\s+/, ' ')
    end
  }
  x.report("gsub2 s") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub(/\s{2,}/, ' ')
    end
  }
  x.report("gsub!2 s") { n.times do
      a_string = "This     is  a test   string."
      a_string.gsub!(/\s{2,}/, ' ')
    end
  }
  x.report("split.join") { n.times do
      a_string = "This     is  a test   string."
      a_string.split.join(' ')
    end
  }
  x.report("squeeze.strip") { n.times do
      a_string = "This     is  a test   string."
      a_string.squeeze(' ').strip
    end
  }
end


$ ./stringcleanup.rb
                     user     system      total        real
gsub             7.250000   0.120000   7.370000 (  8.386002)
gsub!            7.240000   0.130000   7.370000 (  9.007479)
gsub2            7.110000   0.140000   7.250000 (  9.302915)
gsub!2           6.830000   0.150000   6.980000 (  9.309362)
gsub s           7.410000   0.140000   7.550000 ( 10.864572)
gsub! s          7.400000   0.130000   7.530000 ( 10.286886)
gsub2 s          7.020000   0.100000   7.120000 (  8.977424)
gsub!2 s         6.860000   0.100000   6.960000 (  8.421220)
split.join       4.420000   0.110000   4.530000 (  5.716684)
squeeze.strip    3.120000   0.110000   3.230000 (  3.651918)


I haven't run it enough to do any statistical analysis, but after
5 runs it seems like the various flavors of gsub/gsub! don't really
perform any differently.  splitting and squeezing look like much
better options.
Tim G. (Guest)
on 2009-01-11 02:21
(Received via mailing list)
pat eyler wrote:

>> split.join.
>       a_string.gsub(/ +/, ' ')
>     end
>   }
>   x.report("gsub!2 s") { n.times do
>       a_string = "This     is  a test   string."
> gsub2            7.110000   0.140000   7.250000 (  9.302915)
> 5 runs it seems like the various flavors of gsub/gsub! don't really
> perform any differently.  splitting and squeezing look like much
> better options.
>
>
>

Yeah, it doesn't make a huge difference, but it's just a little faster
is all.  Definitely split.join is faster.  squeeze.strip is the fastest
(though that will actually take longer on older versions of ruby).  My
follow up was really just a reference for gsub/gsub!, not that it would
be faster than the other two. :-)
Clifford H. (Guest)
on 2009-01-11 03:20
(Received via mailing list)
pat eyler wrote:
> On Fri, Jan 9, 2009 at 6:20 PM, Clifford H. <removed_email_address@domain.invalid> 
wrote:
>> Robert K. wrote:
>>> I would have guessed that gsub! is fastest
>> It still might be - the benchmark doesn't run long enough to
>> compare the GC overhead of making dozens of little strings
>> that get used once each.
> Is this better?

No. Before I elaborate, I'm not saying I don't believe the result.
I'm saying your benchmark figure won't accurately represent the
cost in a long-running application.

All versions create an initial million strings - perhaps 40 MB.
Your computer has what, 2GB of memory? At what point does the GC run?

The gsub version creates a million extra strings.
The gsub! version creates, perhaps no extra strings, perhaps a million.
The split version creates *six* million extra strings (one per word and
one from join)
The squeeze version creates two million (from squeeze, and from strip).

Now depending on whether the string in your real-life application
is an HTML document with a thousand white-space runs, how many
extra strings do the respective versions take? split makes a *billion*.

A benchmark environment must consider that the code being tested
will run in the context of an application where there are many
other objects created by all the *other* code - perhaps a thousand
times as many objects. At some point, the garbage collector is
likely to run. That takes time, and the time should be part of the
benchmark.

Try squeezing said HTML document a million times, and run the GC
inside each benchmark timer (after the n.times loop). Then I'll
be happy ;-).

Clifford H..
This topic is locked and can not be replied to.