Algorithms.java - finding-duplicates - Micro-benchmarks testing different algorithms of finding duplicates in array

Source path: svn/ trunk/ finding-duplicates/ src/ main/ java/ com/ xemantic/ duplicates/ Algorithms.java

/*
 * This file is part of finding-duplicates.
 *
 * finding-duplicates is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * finding-duplicates is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with finding-duplicates.  If not, see <http://www.gnu.org/licenses/>.
 */
package com.xemantic.duplicates;

import java.util.AbstractList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.TreeSet;

/**
 * Util class containing various duplicate finding algorithms.
 * <p>
 * Created on Jul 11, 2008
 *
 * @author hshsce
 * @version $Id$
 */
public class Algorithms {

	private Algorithms() { /* non-instantiable */ }

	/**
	 * Checks if array contains duplicates using histogram (category <em>histogram</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 *
	 * @param a the array of values to check.
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesHistogram(final int[] a) {
		final boolean[] histogram = new boolean[a.length + 1];
		for (final int value : a) {
			if (histogram[value]) {
				return true;
			}
			histogram[value] = true;
		}
		return false;
	}

	/**
	 * Checks if array contains duplicates using {@link BitSet} (category <em>histogram</em>).
	 * Variation of the {@link #checkDuplicatesHistogram(int[])} algorithm using
	 * more compact data structure.
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesBitSet(final int[] a) {
		final BitSet bits = new BitSet();
		for (final int value: a) {
			if (bits.get(value)) {
				return true;
			}
			bits.set(value);
		}
		return false;
	}

	/**
	 * Checks if array contains duplicates using {@link HashSet} (category <em>set</em>).
	 * <p>
	 * Implementation note: integer array is "casted" into {@link java.util.List}.
     *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesHashSet(final int[] a) {
		return ((new HashSet<Integer>(new AbstractList<Integer>() {
			@Override
			public Integer get(final int index) {
				return a[index];
			}
			@Override
			public int size() {
				return a.length;
			}
		})).size() < a.length);
	}

	/**
	 * Checks if array contains duplicates using {@link TreeSet} (category <em>set</em>).
	 * <p>
	 * Implementation note: integer array is "casted" into {@link java.util.List}.
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesTreeSet(final int[] a) {
		return ((new TreeSet<Integer>(new AbstractList<Integer>() {
			@Override
			public Integer get(final int index) {
				return a[index];
			}
			@Override
			public int size() {
				return a.length;
			}
		})).size() < a.length);
	}

	/**
	 * Checks if array contains duplicates using modulo operation on array elements (category <em>marker</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesModulo(final int[] a) {
		final int n = a.length;
		final int marker = n + 1;
		for (int i = 0; i < n; i++) {
			final int value = a[i] % marker;
			a[value-1] += marker;
		}
		boolean ok = false;
		for (int i = 0; i < n; i++) {
			if (a[i] < marker) {
				ok = true;
			}
			a[i] %= marker;
		}
		return ok;
	}

	/**
	 * Checks if array contains duplicates using modulo operation on array elements - optimized version (category <em>marker</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesModuloOptimized(final int[] a) {
		final int n = a.length;
		final int marker = n + 1;
		for (int i = 0; i < n; i++) {
			final int value = a[i] % marker;
			if (a[value-1] > n) {
				for (int j = 0; j < i; j++) {
					a[(a[j] % marker)-1] %= marker;
				}
				return true;
			}
			a[value-1] += marker;
		}
		for (int i = 0; i < n; i++) {
			a[i] %= marker;
		}
		return false;
	}

	/**
	 * Checks if array contains duplicates using arithmetic progression sum, and factorial of
	 * array elements (category <em>arithmetic</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesSum(final int[] a) {
		final int n = a.length;
		int s = 0;
		long p = 1;
		long f = 1;
		for (int i = 0; i < n; i++) {
			final int value = a[i];
			s += value;
			p *= value;
			f = f * (i + 1);
		}
		final int sum = (n*(n+1))/2;
		return (!((s == sum) && (p == f) ));
	}

	/**
	 * Checks if array contains duplicates summing powers of 2 (category <em>arithmetic</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesPowers(final int[] a) {
		final int n = a.length;
		long sum = 0;
		for (int i = 0; i < n; i++) {
			sum += Math.pow(2, a[i]-1);
		}
		return (sum != (Math.pow(2, n) -1));
	}

	/**
	 * Checks if array contains duplicates summing powers of 2 - optimized version
	 * (category <em>arithmetic</em>).
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesPowersOptimized(final int[] a) {
		final int n = a.length;
		long sum = 0;
		for (int i = 0; i < n; i++) {
			sum += (1L << (a[i]-1));
		}
		return (sum != ((1L << n) -1));
	}

	/**
	 * Checks if array contains duplicates by marking elements with negative sign (category <em>marker</em>).
	 * This algorithm is contributed by Adam Woźniak.
	 *
	 * TODO describe computational complexity in Big-O notation for execution time and memor.
	 * TODO determine max possible element value
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesSign(final int[] a) {
          boolean duplicateFound = false;
          int i;
          for (i = 0; i < a.length; i++) {
        	  final int position = Math.abs(a[i]) - 1;
                if (a[position] < 0) {
                      // It means that we have just found a duplicate.
                      // Further iteration can be obviously skipped.
                      duplicateFound = true;
                      break;
                } else {
                	a[position] = - a[position];
                }
          }

          // Rollback all modifications.
          // Use reversed direction of iteration to increase L1/L2 CPU cache utilization ;)
          // Recently visited array elements (around current value of 'i')
          // probably are still in L1/L2 cache memory.
          for (int j = i-1; j >= 0; j--) {
                final int pos = Math.abs(a[j]) - 1;
                a[pos] = Math.abs(a[pos]);
          }
          return duplicateFound;
    }

	private static final int MASK = ~Integer.MIN_VALUE;

	/**
	 * Checks if array contains duplicates by using the highest bit of elements (category <em>marker</em>).
	 *
	 * TODO determine max possible element value
	 * TODO describe computational complexity in Big-O notation for execution time and memory.
	 *
	 * @param a
	 * @return <code>true</code> if duplicate is found, <code>false</code> otherwise.
	 */
	public static boolean checkDuplicatesHighestBit(final int[] a) {
		for (int i = 0; i < a.length; i++) {
			final int pos = (a[i] & MASK) - 1;
			if (a[pos] < 0) {
				for (int j = 0; j < i; j++) {
					a[(a[j] & MASK)-1] &= MASK;
				}
				return true;
			}
			a[pos] |= Integer.MIN_VALUE;
		}

		for (int i = 0; i < a.length; i++) {
			a[i] &= MASK;
		}
		return false;
	}

}

Show details Hide details

Change log

r3 by hshsce on Jul 12, 2008 Diff

Share project "finding-duplicates" into
"https://finding-
duplicates.googlecode.com/svn"

Go to:

Project members, sign in to write a code review

Older revisions

All revisions of this file

File info

Size: 9227 bytes, 303 lines

View raw file

File properties

svn:mime-type: text/plain