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

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
>