Révision: 2009-10-17 23:00
J'ai l'exécuter sur un grand nombre (par exemple, les chaînes de 20 millions de dollars) et je crois maintenant que cet algorithme n'est pas O(n logn). En dépit de cela, c'est assez cool de mise en œuvre et contient un certain nombre d'optimisations qui permet de courir très vite. Il évalue toutes les dispositions de chaînes binaires 24 ou moins de chiffres en moins de 25 secondes.
J'ai mis à jour le code pour inclure l' 0 <= L < M < U <= X-1 d'observation de plus tôt aujourd'hui.
D'origine
C'est, dans le concept, similaire à une autre question, j'ai répondu. Ce code a également examiné trois valeurs dans une série et de déterminer si un triplet satisfait une condition. Voici le code C# adapté de:
using System;
using System.Collections.Generic;
namespace StackOverflow1560523
{
class Program
{
public struct Pair<T>
{
public T Low, High;
}
static bool FindCandidate(int candidate,
List<int> arr,
List<int> pool,
Pair<int> pair,
ref int iterations)
{
int lower = pair.Low, upper = pair.High;
while ((lower >= 0) && (upper < pool.Count))
{
int lowRange = candidate - arr[pool[lower]];
int highRange = arr[pool[upper]] - candidate;
iterations++;
if (lowRange < highRange)
lower -= 1;
else if (lowRange > highRange)
upper += 1;
else
return true;
}
return false;
}
static List<int> BuildOnesArray(string s)
{
List<int> arr = new List<int>();
for (int i = 0; i < s.Length; i++)
if (s[i] == '1')
arr.Add(i);
return arr;
}
static void BuildIndexes(List<int> arr,
ref List<int> even, ref List<int> odd,
ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
{
for (int i = 0; i < arr.Count; i++)
{
bool isEven = (arr[i] & 1) == 0;
if (isEven)
{
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
even.Add(i);
}
else
{
oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
odd.Add(i);
}
}
}
static int FindSpacedOnes(string s)
{
// List of indexes of 1s in the string
List<int> arr = BuildOnesArray(s);
//if (s.Length < 3)
// return 0;
// List of indexes to odd indexes in arr
List<int> odd = new List<int>(), even = new List<int>();
// evenIndex has indexes into arr to bracket even numbers
// oddIndex has indexes into arr to bracket odd numbers
List<Pair<int>> evenIndex = new List<Pair<int>>(),
oddIndex = new List<Pair<int>>();
BuildIndexes(arr,
ref even, ref odd,
ref evenIndex, ref oddIndex);
int iterations = 0;
for (int i = 1; i < arr.Count-1; i++)
{
int target = arr[i];
bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) ||
FindCandidate(target, arr, even, evenIndex[i], ref iterations);
if (found)
return iterations;
}
return iterations;
}
static IEnumerable<string> PowerSet(int n)
{
for (long i = (1L << (n-1)); i < (1L << n); i++)
{
yield return Convert.ToString(i, 2).PadLeft(n, '0');
}
}
static void Main(string[] args)
{
for (int i = 5; i < 64; i++)
{
int c = 0;
string hardest_string = "";
foreach (string s in PowerSet(i))
{
int cost = find_spaced_ones(s);
if (cost > c)
{
hardest_string = s;
c = cost;
Console.Write("{0} {1} {2}\r", i, c, hardest_string);
}
}
Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
}
}
}
}
Les principales différences sont:
- La recherche Exhaustive de solutions
Ce code génère un ensemble de données pour trouver les plus difficiles d'entrée à résoudre pour cet algorithme.
- Toutes les solutions contre les plus difficiles à résoudre
Le code de la question précédente généré toutes les solutions à l'aide d'un python générateur. Ce code affiche simplement le plus dur pour chaque longueur du motif.
- L'algorithme de Scoring
Ce code vérifie la distance entre le milieu de l'élément à sa gauche et à droite. Le code python testé si une somme a été au-dessus ou au-dessous de 0.
- La Convergence sur un candidat
L'actuel code fonctionne à partir du milieu vers le bord pour trouver un candidat. Le code dans le problème précédent travaillé à partir des bords vers le milieu. Ce dernier changement, donne une grande amélioration de la performance.
- L'utilisation du pair et de l'impair piscines
Sur la base des observations à la fin de cette écriture-up, les recherches les paires de même nombre de paires de nombres impairs pour trouver L et U, en gardant M fixe. Cela réduit le nombre de recherches par pré-informatique. En conséquence, le code utilise deux niveaux d'indirection dans la boucle principale de FindCandidate et nécessite deux appels à FindCandidate pour le milieu de chaque élément: une fois pour le même nombre et une fois pour les impairs.
L'idée générale est de travailler sur des indices, pas le raw de la représentation des données. Le calcul d'un tableau où l'1 apparaissent permet à l'algorithme à exécuter en temps proportionnel au nombre de 1 dans les données, plutôt que dans le temps proportionnel à la longueur des données. C'est une transformation standard: créer une structure de données qui permet une opération plus rapide tout en gardant le problème équivalent.
Les résultats ne sont pas à jour: supprimé.
Edit: 2009-10-16 18:48
Sur les yx de données, qui est un peu plus crédible dans les autres réponses, en tant que représentant de dur des données pour le calcul, j'obtiens ces résultats... j'ai enlevé ces. Ils ne sont pas à jour.
Je tiens à souligner que ces données n'est pas le plus dur pour mon algorithme, donc je pense que l'hypothèse que les yx de fractales sont les plus difficiles à résoudre est erronée. Le pire des cas pour un algorithme particulier, j'attends, dépendra de l'algorithme lui-même et ne sera pas susceptible d'être cohérente à travers les différents algorithmes.
Edit: 2009-10-17 13:30
D'autres observations sur ce point.
Tout d'abord, convertir la chaîne de 0 et de 1 dans un tableau d'index pour chaque position de la 1 du. Dire la longueur de ce tableau est Un X. le but est de trouver
0 <= L < M < U <= X-1
tels que
A[M] - A[L] = A[U] - A[M]
ou
2*A[M] = A[L] + A[U]
Depuis Un[L] et[U] en somme pour un même nombre, ils ne peuvent pas l'être (pair, impair) ou (bizarre, même). La recherche pour un match qui pourrait être amélioré par la division d'Un[] en paires et impaires de piscines et de recherche pour les matches sur Un[M] dans les piscines de paires et impaires candidats à tour de rôle.
Cependant, ce n'est plus de l'optimisation de la performance que d'un algorithme d'amélioration, je pense. Le nombre de comparaisons en baisse, mais de l'ordre de l'algorithme doit être le même.
Edit 2009-10-18 00:45
Encore une autre optimisation se présente à moi, dans la même veine que la séparation de la candidats en paires et impaires. Depuis les trois indices ont pour les ajouter à un multiple de 3 (a, a+x, a+2x -- mod 3 est 0, quel que soit a et x), vous pouvez séparer L, M, et U dans leur mod 3 valeurs:
M L U
0 0 0
1 2
2 1
1 0 2
1 1
2 0
2 0 1
1 0
2 2
En fait, vous pouvez combiner cela avec le pair/impair d'observation et de les séparer dans leur mod 6 valeurs:
M L U
0 0 0
1 5
2 4
3 3
4 2
5 1
et ainsi de suite. Cela permettrait en outre d'optimisation de la performance, mais pas un algorithme rapide.
