473,320 Members | 1,732 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

How to sort a bitset vector quickly?

Hi all,
I want to sort a bitset vector ( bit 1 > bit 0 ), while it seems bitset
doesn't have < or > operation. I tried to use a loop to compare each
bit one by one but it's unbearably slow. Any suggestion?

Jul 23 '05 #1
10 3215
<ha*********@gmail.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...
Hi all,
I want to sort a bitset vector ( bit 1 > bit 0 ), while it seems
bitset
doesn't have < or > operation. I tried to use a loop to compare each
bit one by one but it's unbearably slow. Any suggestion?

You could count the number of zeros and construct a new bitset, with
the number of zeros you counted before and then the rest of ones (exact
number is determined by the size of the original bitset minus the number
of zeros).

hth
--
jb

(reply address in rot13, unscramble first)
Jul 23 '05 #2
* ha*********@gmail.com:
I want to sort a bitset vector ( bit 1 > bit 0 ), while it seems bitset
doesn't have < or > operation. I tried to use a loop to compare each
bit one by one but it's unbearably slow. Any suggestion?


Assuming this is a std::vector< std::bitset<n> >:

std::sort( v.begin(), v.end(), bitsetLess<n> );

where 'bitsetLess' is e.g.

template< unsigned n >
bool bitsetLess( std::bitset<n> const& left, std::bitset<n> const& right )
{
return left.to_ulong() < right.to_ulong();
}

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 23 '05 #3
ha*********@gmail.com scribbled on the stall wall:
Hi all,
I want to sort a bitset vector ( bit 1 > bit 0 ), while it seems bitset
doesn't have < or > operation. I tried to use a loop to compare each
bit one by one but it's unbearably slow. Any suggestion?


WHY?!

the whole purpose of bitsets is that they are generally position
dependent and lose their meaning when reordered.

rethink your reason for doing this.
--
dual 2.8Ghz Xeon; 2GB RAM; 500GB ATA-133; nVidia powered
Linux 2.6.10; glibc-2.3.5; vendor neutral home-brewed installation

----anything after this line is ANNOYING CRAP that the newsserver adds ----
---directly contact newsfeeds and ISPs that piggy back them to complain----
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Jul 23 '05 #4

"Wiseguy" <no***@uber.usachoice.net> wrote in message
news:42**********@spool9-west.superfeed.net...
ha*********@gmail.com scribbled on the stall wall:
Hi all,
I want to sort a bitset vector ( bit 1 > bit 0 ), while it seems bitset
doesn't have < or > operation. I tried to use a loop to compare each
bit one by one but it's unbearably slow. Any suggestion?


WHY?!

the whole purpose of bitsets is that they are generally position
dependent and lose their meaning when reordered.

rethink your reason for doing this.


Perhaps the OP means std::vector< std::bitset<N> >?

Jeff Flinn
Jul 23 '05 #5
Hi Alf,
Your code reflects what I really want to do, thanks. :)
The problem is each bitset contains more than 32*10 bits

Jul 23 '05 #6
* ha*********@gmail.com:

Your code reflects what I really want to do, thanks. :)
The problem is each bitset contains more than 32*10 bits


So?

In the comparision function just loop over the bits till the first
difference.

Alternatively use to_string(), but although that might in practice
be efficient enough it _feels_ so inefficient that no self-respecting
C++ programmer would use it... ;-)
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 23 '05 #7


Alf P. Steinbach wrote:
In the comparision function just loop over the bits till the first
difference.

This is exactly what I did, it's too slow. The vector contains more
than 10 million bitsets, each bitset contains more than 32*10 bits.

Jul 23 '05 #8
[About sorting a vector of bitsets]

* ha*********@gmail.com:
* Alf P. Steinbach wrote:
In the comparision function just loop over the bits till the first
difference.

This is exactly what I did, it's too slow. The vector contains more
than 10 million bitsets, each bitset contains more than 32*10 bits.


Ah. It's time for the Big Revelation (TM). Tweaking the comparision
function will at best buy you a small constant improvement, whereas
optimizing the _algorithm_ and/or _data structure_ can yield really
impressive results.

I think what you've related so far indicates you have a good handle
on the C++ side of things, but that's probably not where the problem
is. There are a number of techniques that can be applied at the C++
level but I fear that if I mention them they'll spur you to blindly
move ahead on a path that doesn't lead to any real solution. So:

What's it all for, i.e. what's the original problem that this huge
vector of bitsets, and sorting of it, is intended to solve?
Cross-posted to [comp.programming], where this probably belongs! ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Jul 23 '05 #9
On 27 May 2005 12:59:29 -0700, ha*********@gmail.com wrote:


Alf P. Steinbach wrote:
In the comparision function just loop over the bits till the first
difference.

This is exactly what I did, it's too slow. The vector contains more
than 10 million bitsets, each bitset contains more than 32*10 bits.


Some thoughts:

1 Can you fit all these bitsets into real memory at one time? If not
then you may want to look at doing an in-memory sort of a chunk of the
bitsets that will fit into memory and then merging the chunks to
produce the final result.

2 How about a radix sort? At each stage partition the current
in-memory chunk by looking at a single bit only. The do a
divide-and-conquer on each half of the result, again looking at only
one bit.

After first pass looking at bit[0]:

0xxxxxxx
..
..
0xxxxxxx
1xxxxxxx
..
..
1xxxxxxx

After second pass, looking at bit[1]:

00xxxxxx
..
..
00xxxxxx
01xxxxxx
..
..
01xxxxxx
10xxxxxx
..
..
10xxxxxx
11xxxxxx
..
..
11xxxxxx

and so on.
rossum

The ultimate truth is that there is no ultimate truth
Jul 23 '05 #10
<ha*********@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
Alf P. Steinbach wrote:
In the comparision function just loop over the bits till the first
difference.

This is exactly what I did, it's too slow. The vector contains more
than 10 million bitsets, each bitset contains more than 32*10 bits.

Unfortunately, std::bitset is not intended as a 'big int' library,
and does not support (efficient) numeric computations.
If I were you I would eventually write a custom bitset class,
and optimize the representation (e.g. endianness, separate
storage of exponent, etc) based on the typical distribution
of values you use.
That is, unless one of the existing 'bigint' packages can do
[but those often use heap-allocated storage, which may cause
performance problems in your case].

This said, have you tried a simple sorting based on to_ulong,
just to verify that performance will be at least satisfying
if you find an efficient comparison method?
I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form


Jul 23 '05 #11

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

Similar topics

2
by: bill | last post by:
Hi, I just spent a loooooooong day to debug a problem, it ended up that sort() does not work properly on my vector!!! In the program I have a vector and the program dynamically add some new...
5
by: Rich S. | last post by:
Hi, Is the code below the best way to have the less than function for an 80 bit bitset or is there something faster / better? When I populate this map with millions (... and millions) of sets...
2
by: Michal Wyrebski | last post by:
Hello, I was thinking how is the fastest and the best way of passing bitset variable to some function. Only one method came to my mind. It's about passing converted value: #v+ void...
8
by: tobias.sturn | last post by:
How would be the best solution to create a dynamic bitset cause with the stl bitset you have to give a number of how big the bitset will be and i dont know the size at the beginning... Thanks...
2
by: ma740988 | last post by:
Given an unsigned int variable that's part of a composite type struct test { unsigned int mask; }; Assume 4 bytes for unsigned int. In one function, I'd like to set any bit or combination...
0
by: ma740988 | last post by:
The code below works and achieves my objective. Something tells me there's a solution that utilizes bitset, hence I'm soliciting a implementation approach (i'm trying to train myself to think C++...
8
by: markww | last post by:
Hi, If I have a vector of structs like this: struct IMAGE { unsigned char *pPix; string strName; int nNumber; };
6
by: zacariaz | last post by:
The subject isnt very clear, but ill do my best to explain. In a class in need a bitset which size is defined by the constructor, e.g. something like this: class Example { std::bitset<?>Bs;...
4
by: Sarath | last post by:
>From the documentation of MSDN, it is saying that bitset is not a STL container Unlike the similar vector<boolClass, the bitset class does not have iterators and is not an Standard Template...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

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.