473,803 Members | 1,992 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

at_most: search "dictionary " for less than or equal

Before I set out to reinvent the wheel.

I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary "; in which case I want a key/value
returned which is the closest key that is less than the search term.
The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.
--
djc
Aug 11 '08 #1
2 1450
slais-www, a BK-tree maybe isn't right what you need but it may be
enough:
http://code.activestate.com/recipes/572156/

Bye,
bearophile
Aug 11 '08 #2
On Aug 11, 9:18 am, slais-www <slais-...@ucl.ac.ukwr ote:
Before I set out to reinvent the wheel.

I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary "; in which case I want a key/value
returned which is the closest key that is less than the search term.

The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.

--
djc
Sounds like you have very long lists to work with. Maybe a solution
using bisect would combine simplest structure with best performance.

-- Paul
Aug 11 '08 #3

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

Similar topics

16
3927
by: Dave Opstad | last post by:
In this snippet: d = {'x': 1} value = d.get('x', bigscaryfunction()) the bigscaryfunction is always called, even though 'x' is a valid key. Is there a "short-circuit" version of get that doesn't evaluate the second argument if the first is a valid key? For now I'll code around it, but this behavior surprised me a bit...
2
7867
by: microsoft | last post by:
When I create a instance of web services proxy in winform, I get the exception. Stack Trace: System.ArgumentException: Item has already been added. Key in dictionary:"winbootdir" Key being added: "winbootdir" at System.Collections.Hashtable.Insert(Object key, Object nvalue, Boolean add) at System.Collections.Hashtable.Add(Object key, Object value)
2
2881
by: Kenneth D Buelow | last post by:
Is there a way to generate a listing of some/all of the "field descriptors" for an ACCESS table? I am a SAS user and am looking for something like SAS's proc CONTENTS which generates a basic "data dictionary" on a SAS dataset. Is there something like this 'built into' MS-ACCESS? Thanks. Ken Buelow
21
13854
by: Helge Jensen | last post by:
I've got some data that has Set structure, that is membership, insert and delete is fast (O(1), hashing). I can't find a System.Collections interface that matches the operations naturally offered by Sets. - ICollection cannot decide containment - IList promises indexability by the natural numbers, which is not achievable (since i hash elements, not sort them). - IDictionary is definatly not setlike. Although I can, of course, define...
1
1429
by: Scott Starker | last post by:
Hi all. I'm a newbie and I am reading "Programming in the Key of C#" by Charles Petzold. I am getting an idea of how C# works and writing a "Hangman" program just for the fun it. But, I am in need of a way to get (randomly) at the dictionary (MS Word?) to find words. Can this be down? Scott
0
4216
by: Ralf Gedrat | last post by:
Hello! I have a Application, this throws after some time following exception: Item has already been added. Key in dictionary: "- 1" key being added: "- 1" I use Application.Run with ApplicationContext. This error message comes from deeper levels must be thrown (mscorlib.dll?!) ?.
1
3133
by: nobrainer | last post by:
Hi, I'm a linguist and have a large self-built bilingual dictionary. I want to turn it into a electronic dictionary, can anyone tell me how to start with it? I've some knowledge in Java programming, but don't know how to write a programme that allows you to search in the large e-file just like a GUI interface e-dictionary. any directions?
2
2113
by: joe.kimbler | last post by:
What is the best way to handle updates in databases with each release of a software package? I used to work on an accounting package in FoxPro that had a "Data Dictionary" and as your code required changes to the database per release, you'd update the Data Dictionary. When you wanted to create a new database, it would create it completely from the data dictionary. If you already had a functional database and the new release required...
0
2300
by: =?Utf-8?B?S2V2aW4gU2NobmVpZGVy?= | last post by:
I have two projects (one using .NET 1.1 the other using 2.0). When I call a particular method in a webservice from the 1.1 project everything works great. When I call the same method from the 2.0 project (identical code) it throws an exception with the message: "{"Item has already been added. Key in dictionary: 'AutoCompleteBackOrders.SopranoWebServices.BaseRequestDTO' Key being added:...
0
9699
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
10542
Oralloy
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...
0
10309
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
10289
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,...
1
7600
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
5496
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...
0
5625
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4274
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
2
3795
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

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.