algorithm - Floating point hash table -


i want construct lookup table using floating point value key. when query table given floating point key, want return value key closest query key.

however don't know beforehand if floating point keys evenly distributed or not.

for example, table might be:

key     value 1.0     "red" 1.25    "blue" 2.0     "green"

if query 1.5, want "blue".

is there way construct table has o(n) memory , o(1) lookup? (that is, hash table). there's o(log(n)) algorithm if store key/value pairs sorted, i'm curious if bound can improved.

you can ignore fact key floating-point number doesn't effect answer. answer same if input 32-bit (equivalent float) or 64-bit (equivalent double) integer. and, believe answer 'no'.

in order find nearest neighbor need keys sorted. when have 32-bit or 64-bit key (it helpful clarify which) means have no choice have sorted data structure (tree? heap? sorted array?) o(log(n)) search in.

it's easy constant-time access specific entry, getting constant-time access nearest neighbor specific entry either requires lookup table 4 billion entries (for floats) or magic.


Comments

Post a Comment

Popular posts from this blog

javascript - jquery or ashx not working -

i using ajax file upload control. it creating html: <form action="/pages/handlers/asyncfileuploadhandler.ashx" method="post" enctype="multipart/form-data" target="ajaxuploader-iframe-1397144545"> <input type="hidden" name="type" value="mindvoice"> <input type="file" id="imagefile" style="display: block; width: 80%; margin-right: auto; margin-left: auto;"> </form> and target is: <iframe width="0" height="0" style="display:none;" name="ajaxuploader-iframe-1397144545" id="ajaxuploader-iframe-1397144545"></iframe> the form submitted using .submit() . my ashx handler: <%@ webhandler language="c#" class="asyncfileuploadhandler" %> using system; using system.web; using nettpals.core; public class asyncfileuploadhandler : ihttphandler { public void processre...
Read more

opencv - DataType<cv::detail::deriv_type>::depth what is it used for -

i wondering why line used in lucas kanade tracker in opencv: datatype<cv::detail::deriv_type>::depth can explain me? in opencv, depth of mat refers type of data contained in mat 's data buffer. represented integer values correspond given data type. these integers commonly abstracted appropriate macro definition (e.g. uchar data represented macro cv_8u ). cv::datatype type-traits class provides method obtain corresponding integer value without having memorize macro means data type. there few cases user code needs use datatype::depth . more common datatype::type . a simple example shows 1 possible use of datatype::depth : cv::mat uchar_data = cv::mat::ones(3, 3, cv_8uc1); cv::mat float_data; uchar_data.convertto(float_data, cv::datatype<float>::depth); // ^^ equivalently replaced // cv_32f macro float_data.at<float>(0,1) += 0.5f; std::cout << float_data << std::endl;...
Read more

python 3.x - Mapping specific letters onto a list of words -

can please suggest approach write piece of codes automatically maps letter in letter_str onto dic_key (a dict key string type contains dashes match length of words in word_lst)? so, mapping occurs if letter appears in every words in list @ same position no matter how many words in list. if no letter appears @ position words in word list new_dic_key '----'. please see examples below thanks word_lst = ['ague', 'bute', 'byre', 'came', 'case', 'doze'] dic_key = '----' letters_str ='abcdefghijklmnopqrstuvwxyz' new_dic_key = '---e' if word_list = ['bute', 'byre'] new_dic_key = 'b--e' or word_list = ['drek', 'drew', 'dyes'] new_dic_key = 'd-e-' if words in word_list of same length code give want: word_list = ['drek', 'drew', 'dyes'] cols = [] in range(len(word_list[0])): cols.append([]) word in ...
Read more