473,837 Members | 1,846 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Hashtable or Btree?

I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? And do you have any implementation you recommend?

Thanks, and merry Christmas folks.

-Dan
Jul 22 '05 #1
4 5253
"Eloff" <da*******@gmai l.com> wrote in message
news:48******** *************** ***@posting.goo gle.com...
I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? Probably hash table.
Note that in this case it is potentially unnecessary to make a
hash table of hash tables - hasing the full URL once might do as well.
And do you have any implementation you recommend?

The pre-standard hash_map or unordered_map that your standard library
implementation is very likely to include should work well.

If anything was to be optimized, it is probably more on the side
of the string storage... eventually.
hth -Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 22 '05 #2
Eloff wrote:
I've got 100MB of urls organized by domain and then by document.
I thought that a hastable of hastables or a btree of btrees
would be a good way to lookup a specific url quickly by first
finding the domain and then finding the matching document. What
do you think would be better? And do you have any implementation
you recommend?


I don't see why you would need containers of containers. Your key could
be the (domain, document) tuple or just the URL, for either hashtables
or btrees.

None of the C++ standard containers sound suitable for this. hash_map
is not standard, and while std::map is, and probably does use a tree,
it is not going to be a btree. Also, those sorts of containers would
build data structures in memory, rather than operating on the file
directly. I don't of know of any popular libraries that would do what
you need either. Most people would just use a database; you could try
Google for "embedded database". I found some in C, but not C++.
--
Dave O'Hearn

Jul 22 '05 #3
"Eloff" <da*******@gmai l.com> wrote in message
news:48******** *************** ***@posting.goo gle.com...
I've got 100MB of urls organized by domain and then by document. I
thought that a hastable of hastables or a btree of btrees would be a
good way to lookup a specific url quickly by first finding the domain
and then finding the matching document. What do you think would be
better? And do you have any implementation you recommend?

Thanks, and merry Christmas folks.

-Dan


I recommend you put your data in a database first. Then you can use any
programming language to search as you please using SQL queries. A good free
database is mysql:

http://www.mysql.com/

--
Cy
http://home.rochester.rr.com/cyhome/
Jul 22 '05 #4
Dave O'Hearn wrote:
...
I don't see why you would need containers of containers. Your key could
be the (domain, document) tuple or just the URL, for either hashtables
or btrees. If you have many documents per domain, it could make sense to organize
the data this way in order to reduce memory consuption.

...
you need either. Most people would just use a database; you could try
Google for "embedded database". I found some in C, but not C++.

sqlite (www.sqlite.org) may be a good choice ...

greetings
Martin
Jul 22 '05 #5

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

Similar topics

5
2066
by: Nobody | last post by:
I am trying to write a BTree class, just wondering if I missed any useful methods. This is my class definition so far (excuse the MFC portions, its a project requirement): template <class TYPE, class ARG_TYPE = const TYPE&> class CBTree : public CObject {
4
2190
by: Spam Me Please | last post by:
I have a tree like this struct BTree{ int left; char c; int right; }; #define END -1 int main(int argc, char *argv)
5
2838
by: francois | last post by:
First of all I would to to apologize for resending this post again but I feel like my last post as been spoiled Here I go for my problem: Hi, I have a webservice that I am using and I would like it to return an XML serialized version of an object.
5
15587
by: Cyrus | last post by:
I have a question regarding synchronization across multiple threads for a Hashtable. Currently I have a Threadpool that is creating worker threads based on requests to read/write to a hashtable. One function of the Hashtable is to iterate through its keys, which apparently is inherently not thread-safe. Other functions of the Hashtable include adding/modifying/deleting. To solve the synchronization issues I am doing two things: 1. Lock...
33
3328
by: Ken | last post by:
I have a C# Program where multiple threads will operate on a same Hashtable. This Hashtable is synchronized by using Hashtable.Synchronized(myHashtable) method, so no further Lock statements are used before adding, removing or iterating the Hashtable. The program runs in a high workload environment. After running a few days, now it suddenly catchs this Exception when inserting a pair of key and object, stacktrace =...
3
9700
by: Fred | last post by:
I'm trying to build a hashtable and a arraylist as object value I'm not able to retrieve stored object from the hashtable. Hashtable mp = new Hashtable(); // THE HASHTABLE ArrayList atemp = new ArrayList(); // THE ARRAY StreamWriter sw = new StreamWriter(@"C:\temp\fred.html");
1
3140
by: Brian Maguire | last post by:
Can too many btree indexes cause page level locking? I read this... http://www.postgresql.org/docs/7.4/static/locking-indexes.html
2
3162
by: PAzevedo | last post by:
I have this Hashtable of Hashtables, and I'm accessing this object from multiple threads, now the Hashtable object is thread safe for reading, but not for writing, so I lock the object every time I need to write to it, but now it occurred to me that maybe I could just lock one of the Hashtables inside without locking the entire object, but then I thought maybe some thread could instruct the outside Hashtable to remove an inside Hashtable...
8
3728
by: chrisben | last post by:
Hi, If I am not sure how many items will be in my Hashtable/ArrayList dynamically (multiple threads can add/remove/check the item), however, I can estimate the total number will not exceed 60000. How much can I gain in term of performance if I decalre the hash as Hashtable h = new Hashtable(60000); instead of
0
9846
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 usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9686
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 synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10581
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 captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10634
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10279
tracyyun
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...
0
9416
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 launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7819
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 instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7007
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();...
0
5675
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 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.