OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 2:09 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: Should there be a degree for robustness?
PostPosted: Thu Jul 19, 2018 8:08 am 
Offline

Joined: Thu May 10, 2018 1:05 pm
Posts: 16
Hello everyone.
I want to begin my question using situations picked from my small project.(you can regard it as an editor with code hinting)
Now I need to implement two features:
1, Key sequence map. Just like vim flavor:
map ^X x
map ^X^A ggvGx
(wrote casually, no special meaning)

2, Object's attribute/method name hint. For example, when you input "string.l", you got prompt menu:
string.length
string.lastIndexOf

To implement these two features, a data struture is needed to collect the key sequences mapped by users(like "^X", "^X^A"), or the attribute names of an object.(like "length", "lastIndexOf")
These are two choice:
1, Common array. Sorted-order-store + Binary search.
2, AVL Tree.

Now my question is, which one is better? The difference is only when on inserting/deleting elements, the latter keeps a stable time and the former is linearly dependent.


An array seems to be more tailored, because, after all, few users customized more than 100 shortcut keys, and few OO objects has more than 100 attributes. Even when they exceed, the performance is still acceptable when less than 1000.


However, if a user really customized more than 1000 shortcut keys, or an OO object really owns more than 1000 attributes, even 10K, 100K, and he felt his program becomes slowly, that would be whose fault? We might complain that the user operated in a strange way, but he might complain about the robustness of our program. After all, if we used AVL Tree instead, all problems would disappear, and the price would not expensive---just introduced some complexity of AVL Tree operation. But if like that, we seemed care about the robustness excessively.

Hope to hear your precious experience, also your choice on the occasions described above.


Top
 Profile  
 
 Post subject: Re: Should there be a degree for robustness?
PostPosted: Thu Jul 19, 2018 12:14 pm 
Offline
Member
Member

Joined: Thu Jul 05, 2007 8:58 am
Posts: 223
Given that you are going to do string matching on the elements, you might want to look into trie data structures. This would allow you to do an O(1) lookup of suggestions after each character entered.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 31 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group