Hi,
I'm interested in details about how sets are implemented in python.
They seem to be quite fast and I found some remarks who state, that
the implementation is highly optimized. I need to implemented sets in
C/C++ and need a starting point on how to do it right. Could somebody
give me a starting point?
regards,
Achim 6 2616
Achim Domma <do***@procoder s.netwrites:
I'm interested in details about how sets are implemented in python.
They seem to be quite fast and I found some remarks who state, that
the implementation is highly optimized. I need to implemented sets
in C/C++ and need a starting point on how to do it right. Could
somebody give me a starting point?
You can simply look at the implementation, Objects/setobject.c in the
Python source code. Most that it's mostly copy-paste from the dict
implementation (dictobject.c) and that both are quite involved and
optimized for the use by Python. They're not general implementation
of sets from use in C.
The "highly optimized" remarks should be understood in the context of
Python, not in the context of other C and C++ set libraries. I don't
know how well Python sets compare to other set libraries, but I doubt
that it's much faster than the median (which "highly optimized" could
be understood to imply).
BTW if you're using C++, why not simply use std::set? If you need it
called from C, you can wrap the needed methods in a C-accessible API.
Hrvoje Niksic <hn*****@xemacs .orgwrote:
>BTW if you're using C++, why not simply use std::set?
Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....
--
\S -- si***@chiark.gr eenend.org.uk -- http://www.chaos.org.uk/~sion/
"Frankly I have no feelings towards penguins one way or the other"
-- Arthur C. Clarke
her nu becomež se bera eadward ofdun hlęddre heafdes bęce bump bump bump
On Jan 4, 9:08 am, Sion Arrowsmith <si...@chiark.g reenend.org.uk>
wrote:
Hrvoje Niksic <hnik...@xemacs .orgwrote:
BTW if you're using C++, why not simply use std::set?
Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....
--
\S -- si...@chiark.gr eenend.org.uk --http://www.chaos.org.u k/~sion/
"Frankly I have no feelings towards penguins one way or the other"
-- Arthur C. Clarke
her nu becomež se bera eadward ofdun hlęddre heafdes bęce bump bump bump
Why cant you implement < for complex numbers? Maybe I'm being naive,
but isn't this the normal definition?
a + bi < c + di iff sqrt(a**2 + b**2) < sqrt(c**2, d**2)
How do you implement a set without sorting?
Are you expecting better than O(log n)?
--Buck
bukzor schrieb:
On Jan 4, 9:08 am, Sion Arrowsmith <si...@chiark.g reenend.org.uk>
wrote:
>Hrvoje Niksic <hnik...@xemacs .orgwrote:
>>BTW if you're using C++, why not simply use std::set?
Because ... how to be polite about this? No, I can't. std::set is crap. The implementation is a sorted sequence -- if you're lucky, this is a heap or a C array, and you've got O(log n) performance. But the real killer is that requirement for a std::set<Tis that T::operator< exists. Which means, for instance, that you can't have a set of complex numbers....
-- \S -- si...@chiark.gr eenend.org.uk --http://www.chaos.org.u k/~sion/ "Frankly I have no feelings towards penguins one way or the other" -- Arthur C. Clarke her nu becomež se bera eadward ofdun hlęddre heafdes bęce bump bump bump
Why cant you implement < for complex numbers? Maybe I'm being naive,
but isn't this the normal definition?
a + bi < c + di iff sqrt(a**2 + b**2) < sqrt(c**2, d**2)
How do you implement a set without sorting?
Are you expecting better than O(log n)?
Of course, hashing does O(1) (most of the time, with a sane hash of course.)
Diez
On Jan 4, 6:08 pm, Sion Arrowsmith <si...@chiark.g reenend.org.uk>
wrote:
Hrvoje Niksic <hnik...@xemacs .orgwrote:
BTW if you're using C++, why not simply use std::set?
Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence -- if you're lucky,
this is a heap or a C array, and you've got O(log n) performance.
But the real killer is that requirement for a std::set<Tis that
T::operator< exists. Which means, for instance, that you can't
have a set of complex numbers....
--
Hallo and Sorry for being OT.
As Arnaud pointed out, you must only overload the < Operator for the
requested type.
Something like
bool operator < ( const Type& fir, const Type& sec )....
similar to python with __lt__ .
The rest of magic will be done by the compiler/interpreter.
Assoziative Arrays (set,map,multi_ set,multi_map) in the classical STL
are implemented as binary trees. Therefore the keys must be comparable
and the access time is O(log n ).
To get a dictionary with O(1), the most STL implementation support a
extension called hash_set.
The new standard TR1 support unsorted_set ... . You can download it
from www.boost.org. Newer gcc runtimes also including the new
subnamespace tr1.
There is no need to implement set in c++ to get O(1).
Greetings Rainer
Sion Arrowsmith:
Because ... how to be polite about this? No, I can't. std::set is
crap. The implementation is a sorted sequence
What about using hash_map instead? You can use it with GCC too (but
you have to use a trick if you want to use string keys).
Bye,
bearophile This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: ForHimself Every Man |
last post by:
What's better about Rattlesnakes than Python. I'm sure there's
something. What is it?
This is not a troll. I'm a snake shooping and I want people's
answers. I don't know beans about Rattlesnakes or have an
preconceived ideas about them. I noticed, however, that everyone I
talk to who are aware of Pythons are also afraid of Rattlesnakes. So
it seems that Rattlesnakes have the potential to compete with and
displace Pythons. I'm...
|
by: f29 |
last post by:
I don't believe that noone has yet spotted that python is becoming
java. Each new version is fully equipped with more garbage than
before. Classes are great, but once there are 1000 of them, inheriting
from each other, I cannot avoid comparing this unpleasant situation to
java.
Python power is in it's syntax, not addons. Let's not copy perl's
experience and one java is already far too much for earth.
f29
|
by: pvinodhkumar |
last post by:
I am reading Lippman's Inside C++ object model.
I feel lonely because the Microsoft C++ compiler which I use does not
provide me an implementation details manual, describing how they
implement vtables in case of single inheritance and multiple
inheritance.
Just to verify what I read is correct I don't have the same from any
other compiler vendors also.
I do not know where CFront's implementation manuals are.
|
by: P Vinodh Kumar |
last post by:
Reposting, please give your ideas/suggestions/comments.
I am reading Lippman's Inside C++ object model.
I feel lonely because the Microsoft C++ compiler which I use does not
provide me an implementation details manual, describing how they
implement vtables in case of single inheritance and multiple
inheritance.
Just to verify what I read is correct I don't have the same from any
|
by: Mathias Panzenboeck |
last post by:
Hi.
I wrote a small hashlib for C. Because I'm new to hashes I looked at pythons implementation and
reused *some* of the code... or more the mathematical "hash-function", not really the code.
In particular I looked at pythons hash and lookup functions, so I came up with this (see the code
underneath).
So, can this code be considered as derived and do I have to put my code under the GPL? I'd like to
publish it under something less...
| |
by: tedpottel |
last post by:
Hi,
I am creating a library of functions. I would like to have them saved
in a sub folder of pythons LIB folder, but I cannot get it to work.
I have a script called test.py
I stored it in LIB folder and typed
Import test, work fine.
I store the script in lib/ted
Then type
|
by: tedpottel |
last post by:
Hi,
I'm trying to create my own lib of functions, but it seems like I can
only import them if they are in pythons lib folder.
Example
I have a folder called
K:\mypython
Now in the interactive python shell I type
|
by: tedpottel |
last post by:
Hi,
Is their a version of pythons IDLE that will run in a dos command
line?
The reason is that I would like to be able to run python code
interactively from my parable by connecting to my desktop using remote
command line or a telnet program.
|
by: Ralph |
last post by:
Hi,
I was reading effictive C++ and some other books again and they all tell
you about hiding implementation details (proxy/pimpl/inheritance) but
they never really explain when to use it.
I am starting on a new project which is part library so I think it would
be good to hide the implementation for the public classes in the library
but this seems a lot of overhead to me (both when developing and runtime
overhead).
|
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, well explore What is ONU, What Is Router, ONU & Routers main usage, and What is the difference between ONU and Router. Lets take a closer look !
Part I. Meaning of...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
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 captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
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 instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
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 the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
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
| |