Benchmark: Compare sorted versus unsorted keys

Script Preparation code:

const alpha = 'abcdefghijklmnopqrstuvwxyz';
const keys = [];

for( let i = 0; i < alpha.length; i++ ) {
  for( let j = 0; j < alpha.length; j++ ) {
    for( let k = 0; k < alpha.length; k++ ) {
  		keys.push( alpha[ i ] + alpha[ j ] + alpha[ k ] );
    }
  }
}

function shuffle(array) {
  let currentIndex = array.length,  randomIndex;

  // While there remain elements to shuffle...
  while (currentIndex != 0) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
      array[randomIndex], array[currentIndex]];
  }

  return array;
}

function fill( obj ) {
  shuffle( keys ).forEach( key => {
    obj[ key ] = key;
  } );
  return obj;
}

function areEquivalent1( value1, value2, stack = [] ) {
  // Numbers, strings, null, undefined, symbols, functions, booleans.
  // Also: objects (incl. arrays) that are actually the same instance
  if ( value1 === value2 ) return true;

  const type1 = typeof value1;

  // Ensure types match
  if ( type1 !== typeof value2 ) return false;

  // Special case for number: check for NaN on both sides
  // (only way they can still be equivalent but not equal)
  if ( type1 === 'number' ) {
    // Failed initial equals test, but could still both be NaN
    return ( isNaN( value1 ) && isNaN( value2 ) );
  }

  // Special case for function: check for toString() equivalence
  if ( type1 === 'function' ) {
    // Failed initial equals test, but could still have equivalent
    // implementations - note, will match on functions that have same name
    // and are native code: `function abc() { [native code] }`
    return value1.toString() === value2.toString();
  }

  // For these types, cannot still be equal at this point, so fast-fail
  if (
    type1 === 'bigint' ||
    type1 === 'boolean' ||
    type1 === 'function' ||
    type1 === 'string' ||
    type1 === 'symbol'
  ) {
    return false;
  }

  // For dates, cast to number and ensure equal or both NaN (note, if same
  // exact instance then we're not here - that was checked above)
  if ( value1 instanceof Date ) {
    if ( !( value2 instanceof Date ) ) {
      return false;
    }
    // Convert to number to compare
    const asNum1 = +value1, asNum2 = +value2;
    // Check if both invalid (NaN) or are same value
    return asNum1 === asNum2 || ( isNaN( asNum1 ) && isNaN( asNum2 ) );
  }

  // At this point, it's a reference type and could be circular, so
  // make sure we haven't been here before... note we only need to track value1
  // since value1 being un-circular means value2 will either be equal (and not
  // circular too) or unequal whether circular or not.
  if ( stack.includes( value1 ) ) {
    throw new Error( `areEquivalent value1 is circular` );
  }

  // breadcrumb
  stack.push( value1 );

  // Handle arrays
  if ( Array.isArray( value1 ) ) {
    if ( !Array.isArray( value2 ) ) {
      return false;
    }

    const length = value1.length;

    if ( length !== value2.length ) return false;

    for ( let i = 0; i < length; i++ ) {
      if ( !areEquivalent1( value1[ i ], value2[ i ], stack ) ) {
        return false;
      }
    }

    // 
    return true;
  }

  // Final case: object

  // get both key lists and check length
  const keys1 = Object.keys( value1 );
  const keys2 = Object.keys( value2 );
  const numKeys = keys1.length;
  
  if ( numKeys !== keys2.length ) {
    return false;
  }

  // Empty object on both sides?
  if ( numKeys === 0 ) {
    return true;
  }

  // sort is a native call so it's very fast - much faster than comparing the
  // values at each key if it can be avoided, so do the sort and then
  // ensure every key matches at every index
  // *** benchmark this vs for (var prop in obj)
  keys1.sort();
  keys2.sort();

  // Ensure perfect match across all keys
  for( let i = 0; i < numKeys; i++ ) {
    if( keys1[ i ] !== keys2[ i ] ) {
      return false;
    }
  }

  // Ensure perfect match across all values
  for( let i = 0; i < numKeys; i++ ) {
    if ( !areEquivalent1( value1[ keys1[ i ] ], value2[ keys1[ i ] ], stack ) ) {
      return false;
    }
  }

  // back up
  stack.pop();

  return true;
}

function areEquivalent2( value1, value2, stack = [] ) {
  // Numbers, strings, null, undefined, symbols, functions, booleans.
  // Also: objects (incl. arrays) that are actually the same instance
  if ( value1 === value2 ) return true;

  const type1 = typeof value1;

  // Ensure types match
  if ( type1 !== typeof value2 ) return false;

  // Special case for number: check for NaN on both sides
  // (only way they can still be equivalent but not equal)
  if ( type1 === 'number' ) {
    // Failed initial equals test, but could still both be NaN
    return ( isNaN( value1 ) && isNaN( value2 ) );
  }

  // Special case for function: check for toString() equivalence
  if ( type1 === 'function' ) {
    // Failed initial equals test, but could still have equivalent
    // implementations - note, will match on functions that have same name
    // and are native code: `function abc() { [native code] }`
    return value1.toString() === value2.toString();
  }

  // For these types, cannot still be equal at this point, so fast-fail
  if (
    type1 === 'bigint' ||
    type1 === 'boolean' ||
    type1 === 'function' ||
    type1 === 'string' ||
    type1 === 'symbol'
  ) {
    return false;
  }

  // For dates, cast to number and ensure equal or both NaN (note, if same
  // exact instance then we're not here - that was checked above)
  if ( value1 instanceof Date ) {
    if ( !( value2 instanceof Date ) ) {
      return false;
    }
    // Convert to number to compare
    const asNum1 = +value1, asNum2 = +value2;
    // Check if both invalid (NaN) or are same value
    return asNum1 === asNum2 || ( isNaN( asNum1 ) && isNaN( asNum2 ) );
  }

  // At this point, it's a reference type and could be circular, so
  // make sure we haven't been here before... note we only need to track value1
  // since value1 being un-circular means value2 will either be equal (and not
  // circular too) or unequal whether circular or not.
  if ( stack.includes( value1 ) ) {
    throw new Error( `areEquivalent value1 is circular` );
  }

  // breadcrumb
  stack.push( value1 );

  // Handle arrays
  if ( Array.isArray( value1 ) ) {
    if ( !Array.isArray( value2 ) ) {
      return false;
    }

    const length = value1.length;

    if ( length !== value2.length ) return false;

    for ( let i = 0; i < length; i++ ) {
      if ( !areEquivalent2( value1[ i ], value2[ i ], stack ) ) {
        return false;
      }
    }

    // 
    return true;
  }

  // Final case: object

  // get both key lists and check length
  const keys1 = Object.keys( value1 );
  const numKeys = keys1.length;
  
  if ( numKeys !== Object.keys( value2 ).length ) {
    return false;
  }

  // Empty object on both sides?
  if ( numKeys === 0 ) {
    return true;
  }

  let matches = 0;
  
  // Ensure perfect match across all keys
  for( let key in value1 ) {
    if( key in value2 ) matches++;
    else return false;
  }
  
  if( matches < numKeys ) return false;

  // Ensure perfect match across all values
  for( let key in value1 ) {
    if ( !areEquivalent2( value1[ key ], value2[ key ], stack ) ) {
      return false;
    }
  }

  // back up
  stack.pop();

  return true;
}

Tests:

sorted keys
const equivalent = areEquivalent1( fill( {} ), fill( {} ) );
for in
const equivalent = areEquivalent2( fill( {} ), fill( {} ) );

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
sorted keys
for in

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model gemma2:9b, generated one year ago):

LLMs can make mistakes. Check important info.

The code you provided implements a recursive function `areEquivalent2` to determine if two values are equivalent.

Here's a breakdown:

**Functionality:**

* **Purpose:** The function aims to compare two values for equality, handling various data types including objects and arrays. It specifically addresses the challenge of circular references, where an object refers back to itself, potentially leading to infinite recursion.
* **Circular Reference Detection:**  The `stack` variable keeps track of already visited values during the recursive process. If a value is encountered again (meaning it's part of a circular reference), an error is thrown to prevent infinite looping.
* **Data Type Handling:** The code distinguishes between different data types:
    * **Arrays:**  It compares the lengths and individual elements of arrays recursively.
    * **Objects:** It iterates through keys, ensuring that both objects have the same keys and values match.

**Potential Improvements:**

1. **Error Message Clarity:** The error message `areEquivalent value1 is circular` could be more informative, specifying the actual involved values for better debugging.

2. **Type Coercion:** Consider handling potential type coercion scenarios (e.g., comparing a number to its string representation) to provide more comprehensive equivalence checks.

3. **Optimization:**  While the `stack` prevents infinite recursion, there might be further optimizations possible depending on the specific use case and data structures involved.

Let me know if you have any other questions or want to explore specific aspects of this code in more detail!

Related benchmarks:

Compare sorted versus unsorted keys (version: 0)

Comparing performance of: sorted keys vs for in

Created: 4 years ago by: Registered User

Jump to the latest result

sorted keys

for in

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

No previous run results

Autogenerated LLM Summary (model gemma2:9b, generated one year ago):