Skip to content

complexity issue in Iterable.iteratesInAnyOrder #224

@DaPutzy

Description

@DaPutzy

The Iterable.iteratesInAnyOrder method suffers from a computational complexity issue that severely impacts performance. Although its fast enough on small lists, its execution time becomes noticeably slower with more than 10 entries and grows to prohibitive lengths with approximately 20 entries (>24h).

Note that the issue only occurs with non-matching lists, if the lists are indeed identical execution time is completly within acceptable limits (~20ms for 20 entries).

Example code to reproduce:

import static org.saynotobugs.confidence.Assertion.assertThat;
import static org.saynotobugs.confidence.core.quality.Iterable.iteratesInAnyOrder;

import java.util.List;

import org.junit.jupiter.api.Test;

class FooTest {

	@Test
	void fails_within_reasonable_amount_of_time() {
		assertThat(
			List.of(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5"
			),
			iteratesInAnyOrder(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5",
				"foo-6"
			)
		);
	}

	@Test
	void fails_but_already_takes_15sec() {
		assertThat(
			List.of(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5",
				"foo-6",
				"foo-7",
				"foo-8",
				"foo-9",
				"foo-10",
				"foo-11"
			),
			iteratesInAnyOrder(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5",
				"foo-6",
				"foo-7",
				"foo-8",
				"foo-9",
				"foo-10",
				"foo-11",
				"foo-12"
			)
		);
	}

	@Test
	void fails_but_takes_3min() {
		assertThat(
			List.of(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5",
				"foo-6",
				"foo-7",
				"foo-8",
				"foo-9",
				"foo-10",
				"foo-11",
				"foo-12"
			),
			iteratesInAnyOrder(
				"foo-1",
				"foo-2",
				"foo-3",
				"foo-4",
				"foo-5",
				"foo-6",
				"foo-7",
				"foo-8",
				"foo-9",
				"foo-10",
				"foo-11",
				"foo-12",
				"foo-13"
			)
		);
	}
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions