returneksibir/yakala — comment on commit d11a69bf12a4cce94f5b7110ca7c69490f2d0390
File:  line 0
By sardok:

BTW i searched for hash functions and there is no indication that
their result suppose to be unique. so you're right. +1 to you cemo!

On Mon, Oct 17, 2011 at 6:56 PM, Sinan Nalkaya wrote:
> Cem, i give up this hash namin discussion, its ok use whatever you want.
>
> But regarding this implementation lets consider these scenarios;
>
> - lets say Set[String] starts to slow down at 1000th member, ok? (i
> dont remember exact number but it should be around that number)
>
> you have 20 sets thats fine. but consider if accidentaly or by chance,
> your string hits 2. Set of the array always. so your 2. Set() hit to
> 1000 but the rest have like 100 for each.
>
> this makes programme slows when you try to save 2.nd Set() which can
> be possible and you can't be sure new link never hit to 2nd array. so
> it is possible that you will see programme slow-down occasionally.
>
> - lets say you are crawling a huge web site which has over 20k links.
> if we are lucky it will distrubute the links very balanced and even
> this case the programme slows down because this all of the sets are
> filled with 1000 links.
>
> the implementation i've done in alt-ref-db does not have this disadvantages.
>
> Here i copy the small class i've done;
>
> sealed class CrawlerLinkDb {
> var db: List[Set[String]] = List(Set.empty)
> val limit = 1000000
>
> def contains(v: String): Boolean = {
> val currDb: Set[String] = db.head
> currDb.contains(v)
> }
>
> def add(v: String) {
> db.foreach{ currDb =>
> if (currDb.contains(v)) {
> true
> }
> }
> if (db.head.size > limit) {
> val newHead: Set[String] = Set.empty
> db = newHead :: db
> }
> db.head.add(v)
> }
>
> def += = this.add _
>
> def size = {
> val sizeList = for (list <- db) yield list.size
> sizeList.sum
> }
> }
>
> this class add's new Set[String] to array when Set hits the limit at
> constant time.
> You save the string at constant time agains since the new empty set is
> always at the beginning.
> This class has a disadvantage about searching the string in the array,
> if there are too many array this may increase searching time.
> i believe this implementation is better than what you did.
>
> btw i run and observed the programme for 3 days, slowness problem
> starts after days.
>
> On Mon, Oct 17, 2011 at 3:45 PM, Cem Eliguzel
>
> wrote:
>> On Mon, Oct 17, 2011 at 3:16 PM, Sinan Nalkaya <
>> reply@reply.github.com>wrote:
>>
>>> 1 - hash function has to generate unique value per string. if you are
>>> saying that i will use strings and i am pretty sure that they will not the
>>> same size and their 1st, 7th and 11th numbers will not be same! i then say
>>> thats ok, but i would not call that a hash function.
>>>
>>
>> [Cem] That's not a correct definition. The only requirement for (at least a
>> trivial) hash function is being deterministic. That is to say, given an
>> input, it always produces the same result.
>> hashCode method of String class returns an integer value. According to your
>> definition, then, we would be allowed to enter only MAX_INT different inputs
>> to the hashCode method. Right?
>>
>> besides that i remember i was talking about saving hash values of the links,
>>> what changed your mind? you were against that idea.
>>>
>> [Cem] Sorry, I remember neither the discussion nor my arguments. By the
>> way, in this proposal there is no such thing as saving hash values.
>>
>> 3 - i will look the code more carefully.
>>> 4 - letme tell you some criterias;
>>> if you can use this as ref db like i did, you may use it in couple of
>>> places, if you provide abstraction, you can change algorithm of saving
>>> method, like using hash or saving some other container other than set for
>>> example.
>>>
>>
>> [Cem] Ok, let's assume that you had a better design. That's nice. The
>> problem is that you haven't come up with a compact solution specific to this
>> problem yet (have you?). We have had to fix it and here is a quick solution
>> that seems to work.
>>
>>>
>>> --
>>> Reply to this email directly or view it on GitHub:
>>>
>>> https://github.com/returneksibir/yakala/commit/d11a69bf12a4cce94f5b7110ca7c69490f2d0390#commitcomment-655693
>>>
>>
>> --
>> Reply to this email directly or view it on GitHub:
>> https://github.com/returneksibir/yakala/commit/d11a69bf12a4cce94f5b7110ca7c69490f2d0390#commitcomment-655755
>>
>