6 ms·

Are we allowed to discuss solution here? Or everybody has to work out the results separately? I don't know Ruby, but I can guess what it is doing basically: 1

by dclara 13y ago

Are we allowed to discuss solution here? Or everybody has to work out the results separately? I don't know Ruby, but I can guess what it is doing basically: 1. Read a list of words from a file with an input path or a default path 2. Take the runtime input from the user with any number of words before carriage return (I guess the words are separated by spaces) 3. Do a loop to compare each of the input words to lower case against the words in the list loaded from the file. If there is a match print out the original word, other wise print out something wrap up the word. It's a O(NxM) algorithm. If the data set is small, we won't see to much difference. Otherwise, we need to concern about better algorithm to improve the speed. 1. Sort the list from the file (remove duplicates) 2. Always check the either half to reduce the number of checking in the list 3. Sort the input list (save the number of duplicates) 4. Print the duplicates directly without comparison again etc. This way the runtime can be improved to O(N*lg M). This may not be the best algorithm. I'd like to hear from you about better solutions.

thezoid 13y ago
Or just populate a hash with the input and see if the entries exist in the hash. If they do print it otherwise print the non matchy one.
- jwcrux 13y ago
  Exactly- hashes and sets are much more efficient than arrays.
  - dclara 13y ago
    Of course. If it's in Java, I'd definitely do that. We are using Hashmap everywhere. Since the original code looks like this, I thought Ruby does not support hash. We usually implement code on the application level, so we don't really care about the underlying algorithms. But if we have to implement on the system level, we do care about the how to manipulate the memory and number of executions, like Big O.
    - goodwink 13y ago
      The original code is like this because it's an exercise. Of course ruby has hashes.
      - dclara 13y ago
        The CTF does not give a description of the problem, but the code instead. And it persuades the new users not to change algorithm too much, just save a few steps, which implies to have minor changes of the code only. Look at my another comment, hash may not be always better than list.
        zwily 13y ago
        Sure a hash isn't always better than a list. In this case, it most definitely is. :)
        dclara 13y ago
        Yes, agreed. I was sort of mislead or implied. It'd be better if CFT can give out the problem description followed by the sample code or don't give any sample code at all. For me, it makes more sense to receive the detailed information, especially the system condition and restriction for trouble shooting and problem solving, followed by brainstorming, instead of going directly to fix code. Because we are used to the pattern to make minimum code change, especially in production. If the code should be completely changed, then we need to know the requirement and re-implement it. Sounds like we have different convention though.
        grey-area 13y ago
        The change required is a tiny one.
        dclara 13y ago
        Unfortunately, I cannot agree with you completely. If there is no language constraint and the system resource constraint, to the problem we have understand so far, using Java will be the fastest and easiest way without hashmap. Load the complete file as a string (depending on how the size of the data set, up to 2^31 - 1), then using string.indexOf() function will get the best result. The underlying algorithm for indexOf() is implemented by JVM in C code which is must fast than any other implementation. My gut told me that it's weird to use hashmap to do string lookup. Everybody knows hashmap is used to lookup key-value pairs. The real reason for not using hashmap here are: 1. hashmap's lookup Big O is O(n), but not the build cost. if the data set size is huge, it takes long time to build the hashmap since every new element exceeded the initialCapacity being added needs a rehash 2. the underlying implementation of indexOf() will use a sort of algorithm called "automata" or something else to do a fast search within a string. So there are lots of alternative solutions. Don't always think there is only one. I'm not in this field, and I'm not interesting to get into to it too much. But I don't think the best answer is that tiny change. This is why I suggested to consider if you are doing application level optimization or changing system level algorithm. Building software is a lot more than code manipulation. Understanding requirement is the first step in the SDLC (Software Development Life Cycle).
  - dclara 13y ago
    Regarding the speed vs memory occupation, there should be comparison between linkedlist vs. hashmap. I remember that linkedlist is faster. So it depends on the language support. You can google it more. I don't have time to find out about the Big O footprint for both now. Here is one link discussing about it: http://stackoverflow.com/questions/7975802/when-to-use-hashmap-over-linkedlist-or-arraylist-and-vice-versa http://stackoverflow.com/questions/7975802/when-to-use-hashm...
    - duaneb 13y ago
      Linear lists are.... linear. Hash maps are constant access. N doesn't need to get very large to see orders of magnitude difference—one you'll certainly see if you switch on level0.
    - cmelbye 13y ago
      A linked list is not faster than a hash in looking up an element. The operation is O(N) for a linked list and O(1) for a hash.
- webreac 13y ago
  That's exactly what I did. My fixed code is smaller than the original code and fast enough to go to level 1. It is in perl (I am not fluent in ruby).
  - dclara 13y ago
    I'd love to know that you have reference to show that with a large amount of data set, hashing is faster than linked list. I don't have the reference at hand, but I know that hashing has a higher cost from speed and memory point of view. I don't see the original code is a huge issue per se which requires 19 levels? of improvement? I'm curious about how you guys move on though. Will appreciate if you can keep post your solution and progress. I guess at the end of the entire program, people may learn how to send the query to multiple indexing servers in a concurrent (I prefer this than "distributed") system and then gather together of all the results. At the end of it, it shows how advanced algorithms Google search engine is used to index terabyte of data. Is that the ultimate solution for a web of data? Take a look of the discussion: http://bit.ly/1f7xIve http://bit.ly/1f7xIve
  - thezoid 13y ago
    I changed one line to make it work faster. From the "best" score I was worse than it by 150 or something. Not that I care really.
    - dclara 13y ago
      Looks like one simple change to hashmap may not be the best answer. May I draw the conclusion from your case like that? The best score now went up to almost 3000. I couldn't imagine how many possible ways out there and one of them could be that excellent. Just curious.
      - platypii 13y ago
        Sorted list + binary search was 2000pts and ran much faster than the hashmap solution.
        13y ago
jaredsohn 13y ago
This solution won't give the correct results because when you sort and count duplicates, the text you output could be in a different order. Edit: And to be clear, you should use the hash solution anyway since it is O(n+m).
- dclara 13y ago
  Nice catch. I should eliminate the sorting on the input words anyways, but save the duplicates in the neighbors, i.e. cache the previous ones. It does not affect the Big O level I mentioned in sorting of the word list loaded from the file. Looks like it's the necessary step.
- dclara 13y ago
  Thank you for giving out the Big O. Now I did the search and found that hash map is O(n) or O(1) here: http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1 http://stackoverflow.com/questions/1055243/is-a-java-hashmap... But I couldn't agree with you about O(n+m) because we cannot hash on the input set as well since that way we will lost the sequence order. Then the caching may help or use LinkedHashmap.
  - jaredsohn 13y ago
    The hash _solution_ is O(n + m) in that it requires iterating through the words read from the dictionary file (O(m)) to fill the hash and then iterating through the inputs (O(n)), each time doing an O(1) hash lookup. You can think of it as: you need to read each word from the dictionary file once and you need to check each input word once; kind of hard to go faster than that.
    - dclara 13y ago
      Yes, I thought about exactly the same way you explained. But my point is trying to save more time, which may or may not be necessary depending on the size of the input data set. If we use caching, we can save the trip to look up the hashmap for each duplicated word of the input. However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.

by dclara 13y ago

thezoid 13y ago

Or just populate a hash with the input and see if the entries exist in the hash. If they do print it otherwise print the non matchy one.

jwcrux 13y ago
Exactly- hashes and sets are much more efficient than arrays.
- dclara 13y ago
  Of course. If it's in Java, I'd definitely do that. We are using Hashmap everywhere. Since the original code looks like this, I thought Ruby does not support hash. We usually implement code on the application level, so we don't really care about the underlying algorithms. But if we have to implement on the system level, we do care about the how to manipulate the memory and number of executions, like Big O.
  - goodwink 13y ago
    The original code is like this because it's an exercise. Of course ruby has hashes.
    - dclara 13y ago
      The CTF does not give a description of the problem, but the code instead. And it persuades the new users not to change algorithm too much, just save a few steps, which implies to have minor changes of the code only. Look at my another comment, hash may not be always better than list.
      - zwily 13y ago
        Sure a hash isn't always better than a list. In this case, it most definitely is. :)
        dclara 13y ago
        Yes, agreed. I was sort of mislead or implied. It'd be better if CFT can give out the problem description followed by the sample code or don't give any sample code at all. For me, it makes more sense to receive the detailed information, especially the system condition and restriction for trouble shooting and problem solving, followed by brainstorming, instead of going directly to fix code. Because we are used to the pattern to make minimum code change, especially in production. If the code should be completely changed, then we need to know the requirement and re-implement it. Sounds like we have different convention though.
        grey-area 13y ago
        The change required is a tiny one.
        dclara 13y ago
        Unfortunately, I cannot agree with you completely. If there is no language constraint and the system resource constraint, to the problem we have understand so far, using Java will be the fastest and easiest way without hashmap. Load the complete file as a string (depending on how the size of the data set, up to 2^31 - 1), then using string.indexOf() function will get the best result. The underlying algorithm for indexOf() is implemented by JVM in C code which is must fast than any other implementation. My gut told me that it's weird to use hashmap to do string lookup. Everybody knows hashmap is used to lookup key-value pairs. The real reason for not using hashmap here are: 1. hashmap's lookup Big O is O(n), but not the build cost. if the data set size is huge, it takes long time to build the hashmap since every new element exceeded the initialCapacity being added needs a rehash 2. the underlying implementation of indexOf() will use a sort of algorithm called "automata" or something else to do a fast search within a string. So there are lots of alternative solutions. Don't always think there is only one. I'm not in this field, and I'm not interesting to get into to it too much. But I don't think the best answer is that tiny change. This is why I suggested to consider if you are doing application level optimization or changing system level algorithm. Building software is a lot more than code manipulation. Understanding requirement is the first step in the SDLC (Software Development Life Cycle).
- dclara 13y ago
  Regarding the speed vs memory occupation, there should be comparison between linkedlist vs. hashmap. I remember that linkedlist is faster. So it depends on the language support. You can google it more. I don't have time to find out about the Big O footprint for both now. Here is one link discussing about it: http://stackoverflow.com/questions/7975802/when-to-use-hashmap-over-linkedlist-or-arraylist-and-vice-versa http://stackoverflow.com/questions/7975802/when-to-use-hashm...
  - duaneb 13y ago
    Linear lists are.... linear. Hash maps are constant access. N doesn't need to get very large to see orders of magnitude difference—one you'll certainly see if you switch on level0.
  - cmelbye 13y ago
    A linked list is not faster than a hash in looking up an element. The operation is O(N) for a linked list and O(1) for a hash.
webreac 13y ago
That's exactly what I did. My fixed code is smaller than the original code and fast enough to go to level 1. It is in perl (I am not fluent in ruby).
- dclara 13y ago
  I'd love to know that you have reference to show that with a large amount of data set, hashing is faster than linked list. I don't have the reference at hand, but I know that hashing has a higher cost from speed and memory point of view. I don't see the original code is a huge issue per se which requires 19 levels? of improvement? I'm curious about how you guys move on though. Will appreciate if you can keep post your solution and progress. I guess at the end of the entire program, people may learn how to send the query to multiple indexing servers in a concurrent (I prefer this than "distributed") system and then gather together of all the results. At the end of it, it shows how advanced algorithms Google search engine is used to index terabyte of data. Is that the ultimate solution for a web of data? Take a look of the discussion: http://bit.ly/1f7xIve http://bit.ly/1f7xIve
- thezoid 13y ago
  I changed one line to make it work faster. From the "best" score I was worse than it by 150 or something. Not that I care really.
  - dclara 13y ago
    Looks like one simple change to hashmap may not be the best answer. May I draw the conclusion from your case like that? The best score now went up to almost 3000. I couldn't imagine how many possible ways out there and one of them could be that excellent. Just curious.
    - platypii 13y ago
      Sorted list + binary search was 2000pts and ran much faster than the hashmap solution.
      - 13y ago

jaredsohn 13y ago

This solution won't give the correct results because when you sort and count duplicates, the text you output could be in a different order. Edit: And to be clear, you should use the hash solution anyway since it is O(n+m).

dclara 13y ago
Nice catch. I should eliminate the sorting on the input words anyways, but save the duplicates in the neighbors, i.e. cache the previous ones. It does not affect the Big O level I mentioned in sorting of the word list loaded from the file. Looks like it's the necessary step.
dclara 13y ago
Thank you for giving out the Big O. Now I did the search and found that hash map is O(n) or O(1) here: http://stackoverflow.com/questions/1055243/is-a-java-hashmap-really-o1 http://stackoverflow.com/questions/1055243/is-a-java-hashmap... But I couldn't agree with you about O(n+m) because we cannot hash on the input set as well since that way we will lost the sequence order. Then the caching may help or use LinkedHashmap.
- jaredsohn 13y ago
  The hash _solution_ is O(n + m) in that it requires iterating through the words read from the dictionary file (O(m)) to fill the hash and then iterating through the inputs (O(n)), each time doing an O(1) hash lookup. You can think of it as: you need to read each word from the dictionary file once and you need to check each input word once; kind of hard to go faster than that.
  - dclara 13y ago
    Yes, I thought about exactly the same way you explained. But my point is trying to save more time, which may or may not be necessary depending on the size of the input data set. If we use caching, we can save the trip to look up the hashmap for each duplicated word of the input. However according to the Big O, linear increase does not count. So the Big O is anyway O(n) when n is near m, it's O(2n) then it's O(n), or n >> m or n << m, it is O(n) or O(m). But runtime, there might be some difference. Again, in most of the normal applications using relational database, we will not use huge memory to store extremely large hashmap. We'll put a cap of the size. Indexing unstructured data is a different story.