473,549 Members | 2,346 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Re: Light slices + COW

That xpairs() generator is nice, but it's not the best possible code
(but you may disagree with me, and you may think that code better than
the successive D code that uses two slices). Inside it I can't use a
list slicing because it copies subparts of the list, probably becoming
too much slow (for example if len(seq) == 1000).
What do you mean by best possible? Most efficient? Most readable? And
why don't you use islice?

eg:

def xpairs(seq):
len_seq = len(seq)
for i, e1 in enumerate(seq):
for e2 in islice(seq, i+1, None):
yield e1, e2

Here's a version which makes more use of itertools. It should be more
efficient, but it's ugly :-) (this is my first time using itertools).

def xpairs(seq):
def _subfunc():
for i in xrange(len(seq) ):
e1 = seq[i]
yield izip(repeat(e1) , islice(seq, i+1, None))
return chain(*_subfunc ())
That D code is as fast or faster than the code you can back-translate
from Python, this is possible because in D arrays slices are very
light, they are a struct of <length, pointer>
D compiles to efficient machine code so Python is at a disadvantage
even if you use the same syntax (see my first example). You can make
the Python version faster, but beware of premature optimization.
I think Python 3.0 too may enjoy a similar strategy of light slices +
COW for strings, lists and arrays (tuples and strings don't need the
COW).
What I'dlike to see is a rope[1] module for Python. I'ts in C++'s STL
library[2], but I haven't found a Python version yet.

[1] http://en.wikipedia.org/wiki/Rope_(computer_science)
[2] http://www.sgi.com/tech/stl/Rope.html

With a Python rope library you could do things like this:

a = '<some extremely long string>'
b = rope(a) # Contains a reference to a
c = b[0:100000] # Get a rope object
d = b[100000:200000] # Get another rope object
e = b + b # Get another rope object
print e # Get the string representation of all the re-assembled sub-sections

# And so on. In the above code there was only 1 copy of the huge
string in memory. The rope objects only contain a tree of
sub-operations (slices, concatenations, references to original
sequences, etc).

This shouldn't be too hard to implement. Does anyone know of an
already-existing 'rope' module?

David.
Jun 27 '08 #1
3 1165
David:
What do you mean by best possible? Most efficient? Most readable?
What's a good wine? It's not easy to define what's "good/best". In
such context it's a complex balance of correct, short, fast and
readable (and more, because you need to define a context. This context
refers to Psyco too).

And why don't you use islice?
You are right, but the purpose of light slices that I have suggested
is to avoid using islice so often. And currently Psyco doesn't digest
itertools well.

D compiles to efficient machine code so Python is at a disadvantage
even if you use the same syntax (see my first example). You can make
the Python version faster, but beware of premature optimization.
This time I don't agree with this "premature optimization" thing. My
original Python version is just 5 lines long, it's readable enough,
and it's a part of a large library of mine of similar functions, they
must be fast because I use them all the time as building blocks in
programs.

What I'dlike to see is a rope[1] module for Python.
People have already suggested it, and there's even an implementation
to replace Python strings. It was refused because... I don't know why,
maybe its implementation was too much more complex than the current
one, and it wasn't faster in all situations (and I think Guido wants
data structures that try to replace the basic built-in ones to be
faster in all situations and user-transparent too).

Bye,
bearophile
Jun 27 '08 #2
D compiles to efficient machine code so Python is at a disadvantage
even if you use the same syntax (see my first example). You can make
the Python version faster, but beware of premature optimization.

This time I don't agree with this "premature optimization" thing. My
original Python version is just 5 lines long, it's readable enough,
and it's a part of a large library of mine of similar functions, they
must be fast because I use them all the time as building blocks in
programs.
Have you looked into the 'numpy' libraries? Those have highly
optimized array/numeric processing functions. Also the have a concept
of getting 'views' when you slice, rather than a full copy.

I also suggest benchmarking your apps which use your libs and see
where the bottlenecks are. Then you can move those to external
compiled modules (c/pyrex/cython/shedskin/etc). You can keep your
slower Python version around as a reference implementation.
What I'dlike to see is a rope[1] module for Python.

People have already suggested it, and there's even an implementation
to replace Python strings. It was refused because... I don't know why,
maybe its implementation was too much more complex than the current
one, and it wasn't faster in all situations (and I think Guido wants
data structures that try to replace the basic built-in ones to be
faster in all situations and user-transparent too).
I'd be happy if there was a separate 'rope' class that you could wrap
arbitrary long sequences in when you need to (the same way that STL
has it separate to the string class, even though the string class has
a lot of other optimizations (internal ref counts, etc, to avoid
unnecessary copies)). Do you know one?

David.
Jun 27 '08 #3
On May 4, 7:49*am, David <wizza...@gmail .comwrote:
*D compiles to efficient machine code so Python is at a disadvantage
*even if you use the same syntax (see my first example). You can make
*the Python version faster, but beware of premature optimization.
*This time I don't agree with this "premature optimization" thing. My
*original Python version is just 5 lines long, it's readable enough,
*and it's a part of a large library of mine of similar functions, they
*must be fast because I use them all the time as building blocks in
*programs.

Have you looked into the 'numpy' libraries? Those have highly
optimized array/numeric processing functions. Also the have a concept
of getting 'views' when you slice, rather than a full copy.

I also suggest benchmarking your apps which use your libs and see
where the bottlenecks are. Then you can move those to external
compiled modules (c/pyrex/cython/shedskin/etc). You can keep your
slower Python version around as a reference implementation.
*What I'dlike to see is a rope[1] module for Python.
*People have already suggested it, and there's even an implementation
*to replace Python strings. It was refused because... I don't know why,
*maybe its implementation was too much more complex than the current
*one, and it wasn't faster in all situations (and I think Guido wants
*data structures that try to replace the basic built-in ones to be
*faster in all situations and user-transparent too).

I'd be happy if there was a separate 'rope' class that you could wrap
arbitrary long sequences in when you need to (the same way that STL
has it separate to the string class, even though the string class has
a lot of other optimizations (internal ref counts, etc, to avoid
unnecessary copies)). Do you know one?

David.
Persistence on the rope class might be trivial; that is, a constant
number of disk modifications be made per state modification.
Jun 27 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
1875
by: thecrow | last post by:
I am trying to figure out how to use hash slices in PHP. (Assign certain values of an associative array into variables, not dependent on loops or internal order of the associative array). In Perl, it would be accomplished like this: %areas = ("atlanta" => "404", "miami" => "305", "manhattan" => "212","Washington DC"=> "202"); print...
17
1694
by: Noam Raphael | last post by:
Hello, Many times I find myself asking for a slice of a specific length, and writing something like l. This happens both in interactive use and when writing Python programs, where I have to write an expression twice (or use a temporary variable). Wouldn't it be nice if the Python grammar had supported this frequent use? My idea is that the...
19
2578
by: David Abrahams | last post by:
Can anyone explain the logic behind the behavior of list slicing with negative strides? For example: >>> print range(10) I found this result very surprising, and would just like to see the rules written down somewhere. Thanks,
29
3377
by: George Sakkis | last post by:
Why does slicing a tuple returns a new tuple instead of a view of the existing one, given that tuples are immutable ? I ended up writing a custom ImmutableSequence class that does this, but I wonder why it is not implemented for tuples. George
1
1307
by: Antoon Pardon | last post by:
I'm for the moment writing two classes. A table, which is like a list, but can start at any integer. A tree which is like a dictionary, but will iterate over the keys in sorted order. The problem is that I would like to implemet slices but, that seems to be impossible with how slices are implemented now.
1
1388
by: meridian | last post by:
If, like me, you're always forgetting which way around your list/seq slices need to go then worry no more. Just put my handy "slice lookupper" (TM) ) on a (large!) PostIt beside your screen and, Hey Presto! no more tediously typing a 1-9 seq into your interpreter and then getting a slice just to check what you get.. (Yes you. You know you do...
3
2406
slightlybefuddled
by: slightlybefuddled | last post by:
(Exporting ImageReady slices as CSS rather than tables) apparently means it'll work just fine in Firefox, but do wacky stuff in IE? Can anyone help me figure out why on earth the slices are not showing up in their proper places in IE(7)? The button bar I created is perfectly set up in Firefox, but when I preview in IE, not so much. The...
31
1701
by: Antoon Pardon | last post by:
The following is part of the explanation on slices in the tutorial: The best way to remember how slices work is to think of the indices as pointing between characters, with the left edge of the first character numbered 0. Then the right edge of the last character of a string of n characters has index n, for example: +---+---+---+---+---+...
5
3830
by: NuberSteve | last post by:
I'm very new to using CSS and also the concept of slices for mouse-overs, and have made my first attempt at using ImageReady to generate slices of a world map. I basically wanted a map that would show various countries appearing to be depressed when "moused-over". To keep it simple at first, I just decided to try two countries. After copying...
0
7546
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7471
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7985
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
6071
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5387
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3517
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1962
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1082
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
784
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.