Skip to content

Optimize FIFOSet#1392

Closed
erikzhang wants to merge 1 commit intomasterfrom
fifoset
Closed

Optimize FIFOSet#1392
erikzhang wants to merge 1 commit intomasterfrom
fifoset

Conversation

@erikzhang
Copy link
Member

Closes #1382, closes #1389

@eryeer Can you test this?

@eryeer
Copy link
Contributor

eryeer commented Jan 2, 2020

Closes #1382, closes #1389

@eryeer Can you test this?

Sure, I'll test it soon.

@eryeer
Copy link
Contributor

eryeer commented Jan 2, 2020

Using the same test code as which is used in #1382 .
The result is:

Add timespan: 6.4464343s
except with timespan: 0.0744838s
contains with timespan: 0.0001441s result: False
contains with timespan: 2E-07s result: True

Faster than original FIFOSet but slower than #1389

Below attaches the test code:

        [TestMethod]
        public void TestFIFOSet()
        {
            Stopwatch stopwatch = new Stopwatch();
            var bucket = new FIFOSet<int>(150_000);
            stopwatch.Start();
            for (int i = 1; i <= 550_000; i++)
            {
                bucket.Add(i);
            }
            stopwatch.Stop();
            Console.WriteLine($"Add timespan: {stopwatch.Elapsed.TotalSeconds}s");
            stopwatch.Reset();
            var items = new int[10000];
            var value = 550_000;
            for (int i = 0; i <= 9999; i++)
            {
                items[i] = value;
                value -= 50;
            }
            stopwatch.Start();
            bucket.ExceptWith(items);
            stopwatch.Stop();
            Console.WriteLine($"except with timespan: {stopwatch.Elapsed.TotalSeconds}s");
            stopwatch.Reset();

            stopwatch.Start();
            var ret = bucket.Contains(140_000);
            stopwatch.Stop();
            Console.WriteLine($"contains with timespan: {stopwatch.Elapsed.TotalSeconds}s result: {ret}");
            stopwatch.Reset();

            stopwatch.Start();
            ret = bucket.Contains(545_001);
            stopwatch.Stop();
            Console.WriteLine($"contains with timespan: {stopwatch.Elapsed.TotalSeconds}s result: {ret}");
            stopwatch.Reset();
        }

@vncoelho
Copy link
Member

vncoelho commented Jan 6, 2020

@eryeer, @erikzhang, looking at the results here: #1389 (comment)

I believe it will be better to move to the "HashSet", a little more complex (almost as in the original, but considerably faster).

Nice job, @eryeer, as always.

@erikzhang erikzhang closed this Jan 7, 2020
@erikzhang erikzhang deleted the fifoset branch January 7, 2020 05:33
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Use List of HashSet to cache hashes instead of OrderedDictionary in FIFOSet

3 participants