Simple Sorting Facade for Java (SSF4J)

In Java to sort two or more lists together you have to write a custom solution.

Say, you have list of names and corresponding list of weights. There is no API that allows you to sort names by weights (at least not that I know). However this is very common use case, especially when you analyzing data in your programs.

To achieve this, you, most likely, implement one of the sorting algorithms with a custom swap-logic.

Simple sorting facade is a pattern that already contains implementation of sorting algorithm(s) and only requires developers to specify source list, its bounds, and compare- and the swap-logic.

You can explore SSF4J on GitHub and contribute your implementations of sorting algorithms.

Here's an example of using SSF4J:

МОДИФИКАЦИЯ АЛГОРИТМА ТОРБЕНА ДЛЯ ПОИСКА МЕДИАНЫ В БОЛЬШОМ ОДНОМЕРНОМ МАССИВЕ

Выкладываю статью, как и обещал в предыдущем посте.

МОДИФИКАЦИЯ АЛГОРИТМА ТОРБЕНА ДЛЯ ПОИСКА МЕДИАНЫ В БОЛЬШОМ ОДНОМЕРНОМ МАССИВЕ
Гусев Д.И.
Владимирский государственный университет

Аннотация
В статье предлагается алгоритм поиска медианы, основанный на известном алгоритме Торбена. Особенностью обоих алгоритмов является то, что при поиске медианы они не требует изменения исходного массива и позволяют читать весь массив последовательно. Приводятся характеристики предлагаемого алгоритма, которые при определенных параметрах показывают производительность более 40% относительно алгоритма Торбена.

Скачать: Текст статьи (241 КБ)

Histogram-based median search

Реализация алгоритма поиска медианы в большом одномерном массиве чисел.
Это измененный вариант известного алгоритма Торбена.
Привожу этот алгоритм здесь, чтобы на него можно было сослаться.
Сам алгоритм приводится без пояснений, пояснения и характеристики производительности позже выложу здесь же в виде статьи.

package anjlab.cubics.aggregate.median; import java.util.Arrays; /**  * Histogram-based implementation of median search algorithm.  *   * Based on N. Devillard's implementation of Torben Mogensen's algorithm   * ({@linkplain http://ndevilla.free.fr/median/median.pdf}).  *   * @author Dmitry Gusev   */ public class HistogramBasedMedianFinder {   private final int K;  //  number of ranges to create in histogram   private final double epsilon;      public HistogramBasedMedianFinder() {     this(15, 0.000000001d);   }      public HistogramBasedMedianFinder(int k, double epsilon) {     this.K = k;     this.epsilon = epsilon;   }      public double search(double[] m) {     int n = m.length;     int correction = n % 2 == 0 ? 1 : 0;     double min, max;     min = max = m[0];     for (int i = 1; i < n; i++) {       if (m[i] < min) min = m[i];       if (m[i] > max) max = m[i];     }     long leftOutRange = 0;     long rightOutRange = 0;     Histogram histogram = new Histogram();          while (true) {       histogram.init(min, max);              for (int i = 0; i < n; i++) {         histogram.add(m[i]);       }       long countInRanges = histogram.totalCount - histogram.others;       if (countInRanges == 1) {         return histogram.recentlyAdded;       }       long incCount = 0;              for (int i = 0; i < histogram.rangeCount; i++)  {         long rangeCount = histogram.counts[i];                  incCount += rangeCount;                  long rightOutCurrentRange = (countInRanges + rightOutRange) - incCount;                if (incCount + leftOutRange >= rightOutCurrentRange - correction) {           //  Median is in this range. Repeat search in this range           min = i == 0 ? histogram.start : histogram.ranges[i - 1];           max = histogram.ranges[i];                  if (almostSame(min, max)) {             return min;           }                      leftOutRange += (incCount - rangeCount);            rightOutRange = rightOutCurrentRange;                      break;         }       }     }   }      public boolean almostSame(double a, double b) {     return Math.abs(a - b) < epsilon;   }      private class Histogram {     public double start;     public double end;     private double step;     public double[] ranges = new double[K + 1];     public long[] counts = new long[K + 1];     public double recentlyAdded;     public long totalCount;     public long others;     public int rangeCount;     public void init(double start, double end) {       this.start = start;       this.end = end;       Arrays.fill(counts, 0);       others = 0;       totalCount = 0;       if (end < start || almostSame(start, end)) {         rangeCount = 0;       } else {         this.step = (end - start) / K;         int idx = 0;         for (double i = start; i < end; i += step) {           double right = i + step;           if (right > end) {             right = end;           }           ranges[idx++] = right;         }         rangeCount = idx;       }     }     public void add(double value) {       totalCount++;       if (value < start || value > end) {         others++;         return;       }       recentlyAdded = value;       //  binary search              int low = 0;       int high = rangeCount - 1;       while (low <= high) {         int mid = (high + low) >>> 1;         if (value <= ranges[mid]) {           if (mid > 0 && value < ranges[mid - 1]) {             high = mid - 1;  //  continue search           } else {             counts[mid]++;  //  we've found the range             return;           }         } else if (value > ranges[mid]) {           low = mid + 1;         }       }     }   }   }

.Net Collections Lookup Performance

using System;
using System.Collections.Generic;
using System.Linq;
using NUnit.Framework;

namespace TechNoir.NorCal.BL.Tests
{
    [TestFixture]
    public class PerformanceTests
    {
        [Test]
        public void CompareLookupSpeed()
        {
            bool warmUp = true;

            for (int j = 1; j <= 10; j++)
            {
                int n = j * 1000;

                Console.WriteLine("\nTest {0}; n = {1}\n", j, n);

                List<int> list;
                Dictionary<int, object> dictionary;
                List<int> sortedList;
                IQueryable<int> queryable;

                PrepareTestData(n, 
                    out list, out dictionary, out sortedList, out queryable);


                DateTime start = DateTime.Now;
                foreach (int item in list)
                {
                    Assert.That(dictionary.ContainsKey(item));
                }
                DateTime end = DateTime.Now;

                Console.WriteLine("IDictionary.ContainsKey : " 
                    + (end - start).TotalMilliseconds);


                start = DateTime.Now;
                foreach (int item in list)
                {
                    Assert.That(sortedList.BinarySearch(item) != -1);
                }
                end = DateTime.Now;

                Console.WriteLine("List.BinarySearch       : " 
                    + (end - start).TotalMilliseconds);


                start = DateTime.Now;
                foreach (var item in list)
                {
                    Assert.That(list.Contains(item));
                }
                end = DateTime.Now;

                Console.WriteLine("List.Contains           : " 
                    + (end - start).TotalMilliseconds);


                start = DateTime.Now;
                if (j <= 3)
                {
                    foreach (int item in list)
                    {
                        int localItem = item;
                        Assert.That(queryable.Any(i => i == localItem));
                    }
                }
                end = DateTime.Now;

                Console.WriteLine("IQueryable.Any          : " 
                    + (end - start).TotalMilliseconds);


                if (warmUp)
                {
                    warmUp = false;
                    j--;
                }

            }
        }

        private static void PrepareTestData(
            int n, 
            out List<int> list, 
            out Dictionary<int, object> dictionary, 
            out List<int> sortedList, 
            out IQueryable<int> queryable)
        {
            list = new List<int>();

            var rand = new Random(42);

            for (int i = 0; i < n; i++)
            {
                int x;
                do
                {
                    x = rand.Next(int.MaxValue);
                } while (list.Contains(x));

                list.Add(x);
            }

            queryable = list.AsQueryable();

            dictionary = new Dictionary<int, object>();

            foreach (var item in list)
            {
                dictionary.Add(item, null);
            }


            sortedList = new List<int>();
            sortedList.AddRange(list);

            sortedList.Sort();
        }
    }
}

AddOne

Problem

Implement C# function int addone(int n) which will return n+1. You can NOT use any of the following arithmetical operations in the fuction body: + - * / ++ -- += -=.

Solution

using NUnit.Framework;

namespace Developer.Test.Net
{
    [TestFixture]
    public class TestModulus
    {
        [Test]
        public void TestAddOne()
        {
            for (int i = -1000; i < 1000; i++)
            {
                Assert.AreEqual(i + 1, AddOne(i));
            }

            int j = int.MaxValue;

            Assert.AreEqual(j + 1, AddOne(j));

            j = int.MinValue;

            Assert.AreEqual(j + 1, AddOne(j));
        }

        public static int AddOne(int n)
        {
            int position = 1;

            while (position != 0)
            {
                if ((n & position) == position) {
                    n = n ^ position;
                } else {
                    n = n | position;

                    break;
                }

                position = position << 1;
            }

            return n;
        }
    }
}