Shifting array element & regex on array element 
Author Message
 Shifting array element & regex on array element

In implementing a buffer gap mechanism, I was wondering if there is
any efficient way to shift elements in an array.

Suppose that I have 80000 elements in an array. I would like to insert
a new element between the 1st and 2nd elements by making the 2nd
element be the 3rd and so on.

In C, the way to do this is to do bcopy/memmove or
something like while (--1 >= 0) *--to = *--from;

The way I am implementing right now is:
80000.downto(2) {|i| array[i+1]=array[i]}

1. Is this as efficient as it gets? It looks fast enough so far.

The next future of the buffer is that it supports regex. Ruby's
standard Regex class can't operate over array, especially array with a
gap.

2. Anyone know of a Regex library that can operate over an array (either
   Ruby's Array or C's array (unsigned char*) ) with a gap?

TIA,
YS.



Tue, 02 Nov 2004 18:47:47 GMT  
 Shifting array element & regex on array element
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quote:

> In implementing a buffer gap mechanism, I was wondering if there is
> any efficient way to shift elements in an array.

> Suppose that I have 80000 elements in an array. I would like to insert
> a new element between the 1st and 2nd elements by making the 2nd
> element be the 3rd and so on.

> In C, the way to do this is to do bcopy/memmove or
> something like while (--1 >= 0) *--to = *--from;

> The way I am implementing right now is:
> 80000.downto(2) {|i| array[i+1]=array[i]}

> 1. Is this as efficient as it gets? It looks fast enough so far.

Perhaps ugly? But it works.

irb(main):015:0> array = [1, 3, 4, 5]
[1, 3, 4, 5]
irb(main):023:0> array[0..0] + [2] + array[1..-1]
[1, 2, 3, 4, 5]

Quote:
> The next future of the buffer is that it supports regex. Ruby's
> standard Regex class can't operate over array, especially array with a
> gap.

> 2. Anyone know of a Regex library that can operate over an array (either
>    Ruby's Array or C's array (unsigned char*) ) with a gap?

> TIA,
> YS.

I'm not sure what you mean here.

- --
Signed,
Holden Glova
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE85Od2+mF116Lw2cQRAnXWAJ91fkiQbPNR+3jn0nygSCNfrQygyACeI/ge
/gd2nx50+4SY0fH2J399+1g=
=uQTZ
-----END PGP SIGNATURE-----



Tue, 02 Nov 2004 19:24:22 GMT  
 Shifting array element & regex on array element
Azt irtad, hogy

Quote:


>> > The way I am implementing right now is:
>> > 80000.downto(2) {|i| array[i+1]=array[i]}
>> irb(main):023:0> array[0..0] + [2] + array[1..-1]
>> [1, 2, 3, 4, 5]

What about a[1...1]=2

Seems to work for me...

Gergo


|  URL:   turul.eet.bme.hu/~kgergely    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net



Tue, 02 Nov 2004 23:43:17 GMT  
 Shifting array element & regex on array element

Quote:


> > The way I am implementing right now is:
> > 80000.downto(2) {|i| array[i+1]=array[i]}
> irb(main):023:0> array[0..0] + [2] + array[1..-1]
> [1, 2, 3, 4, 5]

Wow, this is cleaner and I don't see any difference in performance to
my approach. I'll choose your approach. Thanks!

Quote:
> > 2. Anyone know of a Regex library that can operate over an array (either
> >    Ruby's Array or C's array (unsigned char*) ) with a gap?
> I'm not sure what you mean here.

Perhaps you know buffer gap by other name because I don't know the
appropriate term for this (I made up the term buffer gap). In text
editing, the most efficient, both in terms of space and computation,
model for storing the text is a buffer with a gap. A buffer is simply
a long sequential storage (array). If the text is put in a buffer
without a gap, insertion and deletion operations will be expensive
because of the constant element shifting.

So, a gap at the currently operated character is created. The gap is
set to, say 20-30 characters. So, insertion will simply consume the
gap and deletion will simply enlarge the gap. This strategy postpones
the shifting and the mapping from the underlying storage to what the
user sees is simple and fast. The gap takes advantage of the locality
behaviour of human editing.

But when asked to perform a regex search, the regex code must be able
to ignore the gap. Some text are to the left of the gap and some more
to the right. The regex code must be able to evaluate the whole text
as if the gap is not there. That's what I mean by a Regex library that
can operate over a gap, or on two disjointed memory ranges.

TIA,
YS.



Wed, 03 Nov 2004 00:51:52 GMT  
 Shifting array element & regex on array element
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Quote:

> Azt irtad, hogy



> >> > The way I am implementing right now is:
> >> > 80000.downto(2) {|i| array[i+1]=array[i]}

> >> irb(main):023:0> array[0..0] + [2] + array[1..-1]
> >> [1, 2, 3, 4, 5]

> What about a[1...1]=2

> Seems to work for me...

I'll be damned. How this works doesn't make any sense to me. To me that
reads; from the 1 position upto but excluding the 1 position, put a value (2
in this case).

The same can be done with something like array[1,0]=2 as was pointed out by
Rennex on IRC #ruby-lang. To me that reads; from the 1 position with a length
of 0 assign the value. I'm almost reading this as a 1/2 element index - from
a readability point of view to me it just doesn't make sense.

Can anyone help me understand it from a readability POV? Some on irc have
tried to explain it in implementation terms but when I'm coding in Ruby I'm
not thinking about how it is understood in Ruby, more about how it reads in
Ruby. Any help is welcomed. Thank you.

- --
Signed,
Holden Glova
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE85aqL+mF116Lw2cQRAuqpAJ9ij7aIzYZn+YZP6dPe7fquVF8kMgCgjhK9
ginaKAtv/tdUV5nxDkBx8So=
=SvPw
-----END PGP SIGNATURE-----



Wed, 03 Nov 2004 09:17:38 GMT  
 Shifting array element & regex on array element

Quote:
> > What about a[1...1]=2

> > Seems to work for me...

> I'll be damned. How this works doesn't make any sense to me. To me that
> reads; from the 1 position upto but excluding the 1 position, put a value (2
> in this case).

> The same can be done with something like array[1,0]=2 as was pointed out by
> Rennex on IRC #ruby-lang. To me that reads; from the 1 position with a length
> of 0 assign the value. I'm almost reading this as a 1/2 element index - from
> a readability point of view to me it just doesn't make sense.

> Can anyone help me understand it from a readability POV? Some on irc have
> tried to explain it in implementation terms but when I'm coding in Ruby I'm
> not thinking about how it is understood in Ruby, more about how it reads in
> Ruby. Any help is welcomed. Thank you.

IMHO, it's a bug as it breaks the contract for Range:

(1...1).size            # => 0
(1...1).begin           # => 1
(1...1).end             # => 1   <-- should be 0!

-- Dossy

--

Panoptic Computer Network             web: http://www.panoptic.com/
  "He realized the fastest way to change is to laugh at your own
    folly -- then you can let go and quickly move on." (p. 70)



Wed, 03 Nov 2004 09:29:52 GMT  
 Shifting array element & regex on array element

Quote:


> > > What about a[1...1]=2

> > > Seems to work for me...

> IMHO, it's a bug as it breaks the contract for Range:

> (1...1).size            # => 0
> (1...1).begin           # => 1
> (1...1).end             # => 1   <-- should be 0!

>From ri Range I get the following:

------------------------------------------------------------------------
     ===, begin, each, end, exclude_end?, first, last, length, new, size
------------------------------------------------------------------------

the Range#exclude_end? indicates to me that

  (1..2) and (1...2) have the same #end value, but
  different lengths/sizes.

irb(main):001:0> r=1..2
1..2
irb(main):002:0> s=1...2
1...2
irb(main):003:0> p r.end; p r.size
2
2
nil
irb(main):004:0> p s.end; p s.size
2
1

--
Jim Freeze
If only I had something clever to say for my comment...
~



Wed, 03 Nov 2004 09:48:51 GMT  
 Shifting array element & regex on array element

Quote:
> the Range#exclude_end? indicates to me that

>   (1..2) and (1...2) have the same #end value, but
>   different lengths/sizes.

Oh, eek.  Well, what's Array#[obj] do?  If the obj is a Range,
it only looks at obj.begin?

-- Dossy

--

Panoptic Computer Network             web: http://www.panoptic.com/
  "He realized the fastest way to change is to laugh at your own
    folly -- then you can let go and quickly move on." (p. 70)



Wed, 03 Nov 2004 09:54:04 GMT  
 Shifting array element & regex on array element

Quote:

> Azt irtad, hogy


>>> > The way I am implementing right now is:
>>> > 80000.downto(2) {|i| array[i+1]=array[i]}
>>> irb(main):023:0> array[0..0] + [2] + array[1..-1]
>>> [1, 2, 3, 4, 5]
> What about a[1...1]=2
> Seems to work for me...

First neat use I've seen for ...

--
Martin DeMello



Wed, 03 Nov 2004 17:02:19 GMT  
 Shifting array element & regex on array element
Quote:


> > the Range#exclude_end? indicates to me that

> >   (1..2) and (1...2) have the same #end value, but
> >   different lengths/sizes.

> Oh, eek.  Well, what's Array#[obj] do?  If the obj is a Range,
> it only looks at obj.begin?

No, it returns an array.

a=%w{one two three} #=>  ["one", "two", "three"]
a[1..2]             #=>  ["two", "three"]

--
Jim Freeze
If only I had something clever to say for my comment...
~



Thu, 04 Nov 2004 00:48:07 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. Arrays: Build array in multiple for loops or replace array elements

2. Adding an element in an array of cluster of 2 elements

3. shifting array elements, part two

4. shifting array elements

5. Access Array Elements by Arrays Reference

6. for every element of array find bounds in another array

7. Array and creation of the elements of the array

8. Adjustable array dimensions specified via array element?

9. creation of array elements and write traces on an array

10. selecting array elements with a logical array

11. (typep (make-array 10 :element-type 'bit) '(array bit (10)))

12. Do array element traces affect the whole array?

 

 
Powered by phpBB® Forum Software