6 ms·

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.

by thezoid 13y ago

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).
  - lhc- 13y ago
    You dont have to use Ruby. I actually did it in Python because I dont know Ruby. Just had to change the !# and fiddle around a little with the input reading.
    - dclara 13y ago
      Thank you for your advice, I'm really new to this game and I even don't know how to use github. Don't laugh at me, because I have enough experience on coding by myself and reading/modifying other people's code. I don't have time to play coding on CTF, but I'm curious about how other people are thinking about it, especially about distributed system. Coding is the last thing we need to concern since various languages are available to implement. System architecture design, data modeling, application performance, security and algorithms are more important. Regarding the language itself, I understand that Ruby and Python are quick and easy, but that's not for real production systems. Lots of teenagers are using it now. Maybe you are not happy to hear like that. Here are two blog articles regarding it: http://bingobo.info/blog/contents/do-not-rely-on-other-platforms-or-tools-than-a-vanilla-hosting-environment-for-production.jsp http://bingobo.info/blog/contents/do-not-rely-on-other-platf... http://bingobo.info/blog/contents/having-a-solid-foundation-makes-you-worry-free.jsp http://bingobo.info/blog/contents/having-a-solid-foundation-...
      - al2o3cr 13y ago
        LOL @ "don't let other people control your tools" and then going straight into "how to set up your Windows environment" in the next post after one of your links.
        dclara 13y ago
        Thanks for reading. Is there any conflict between the two? The original words was "You're giving them a throat to choke". The minimum set of tools is always necessary either on Windows or Linux, especially from Open Source. Just make sure don't take the risk of your application to do re-implementation later.
      - grey-area 13y ago
  - brown9-2 13y ago
    http://www.ruby-doc.org/stdlib-2.1.0/libdoc/set/rdoc/Set.html http://www.ruby-doc.org/stdlib-2.1.0/libdoc/set/rdoc/Set.htm...
    - dclara 13y ago
      Thanks a lot for your reference. A couple days ago, I was almost convinced to use GO after I took a look about half of its examples. People said, we are not going to catch up the languages which are changed every 6 months. The same applied for Javascript and JQuery, you don't really need the latter, and there are so many JavaScript libraries. Once you change your job, you may abandon some of them. Look at my another comment. For the same reason, I'm not going to take time to learn a new language.
- 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

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.

by 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).
- lhc- 13y ago
  You dont have to use Ruby. I actually did it in Python because I dont know Ruby. Just had to change the !# and fiddle around a little with the input reading.
  - dclara 13y ago
    Thank you for your advice, I'm really new to this game and I even don't know how to use github. Don't laugh at me, because I have enough experience on coding by myself and reading/modifying other people's code. I don't have time to play coding on CTF, but I'm curious about how other people are thinking about it, especially about distributed system. Coding is the last thing we need to concern since various languages are available to implement. System architecture design, data modeling, application performance, security and algorithms are more important. Regarding the language itself, I understand that Ruby and Python are quick and easy, but that's not for real production systems. Lots of teenagers are using it now. Maybe you are not happy to hear like that. Here are two blog articles regarding it: http://bingobo.info/blog/contents/do-not-rely-on-other-platforms-or-tools-than-a-vanilla-hosting-environment-for-production.jsp http://bingobo.info/blog/contents/do-not-rely-on-other-platf... http://bingobo.info/blog/contents/having-a-solid-foundation-makes-you-worry-free.jsp http://bingobo.info/blog/contents/having-a-solid-foundation-...
    - al2o3cr 13y ago
      LOL @ "don't let other people control your tools" and then going straight into "how to set up your Windows environment" in the next post after one of your links.
      - dclara 13y ago
        Thanks for reading. Is there any conflict between the two? The original words was "You're giving them a throat to choke". The minimum set of tools is always necessary either on Windows or Linux, especially from Open Source. Just make sure don't take the risk of your application to do re-implementation later.
    - grey-area 13y ago
- brown9-2 13y ago
  http://www.ruby-doc.org/stdlib-2.1.0/libdoc/set/rdoc/Set.html http://www.ruby-doc.org/stdlib-2.1.0/libdoc/set/rdoc/Set.htm...
  - dclara 13y ago
    Thanks a lot for your reference. A couple days ago, I was almost convinced to use GO after I took a look about half of its examples. People said, we are not going to catch up the languages which are changed every 6 months. The same applied for Javascript and JQuery, you don't really need the latter, and there are so many JavaScript libraries. Once you change your job, you may abandon some of them. Look at my another comment. For the same reason, I'm not going to take time to learn a new language.
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