मैं एक छोटे से आवेदन है कि एक खोज एल्गोरिथ्म अनुकूलन दर्शाता बनाई गई है। यदि आप यही चाहते हैं तो कृपया मुझे बताएं।
नोट्स:
- कार्यक्रम एक वर्ग मैट्रिक्स
- बनाता है पढ़ने की सुगमता के लिए, मैं डेटा के साथ काम करने के लिए संग्रह का उपयोग कर रहा हूँ। मेरा मानना है कि प्रसंस्करण में एक अधिभार है, लेकिन मैं सिर्फ सिद्धांत को इंगित करने की कोशिश कर रहा हूं।
संदेश यह है:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Program
{
class Matrix
{
public int[][] JaggedInteger2DMatrix { get; set; }
public List<MatrixCell> Cells { get; set; }
public List<MatrixLine> Lines { get; set; }
public int Width { get; set; }
public int Height { get; set; }
public Matrix(int size, int seed)
{
var r = new Random(seed);
int[][] jaggedInteger2DMatrix = new int[size][];
for (int i = 0; i < size; i++)
{
jaggedInteger2DMatrix[i] = new int[size];
for (int j = 0; j < size; j++)
{
jaggedInteger2DMatrix[i][j] = r.Next(2);
//Console.Write(jaggedInteger2DMatrix[i][j]+" ");
}
//Console.Write("\r\n");
}
InitializeMatrix(jaggedInteger2DMatrix);
}
public Matrix(int[][] jaggedInteger2DMatrix)
{
InitializeMatrix(jaggedInteger2DMatrix);
}
private void InitializeMatrix(int[][] jaggedInteger2DMatrix)
{
JaggedInteger2DMatrix = jaggedInteger2DMatrix;
Height = jaggedInteger2DMatrix.GetLength(0);
Width = jaggedInteger2DMatrix[0].GetLength(0);
Cells = new List<MatrixCell>();
Lines = new List<MatrixLine>();
int horizontalLineCounter = 0;
MatrixCell matrixCell = null;
foreach (var horizontalLine in jaggedInteger2DMatrix)
{
int verticalLineCounter = 0;
foreach (var cell in horizontalLine)
{
matrixCell = new MatrixCell()
{
HorizontalLineIndex = horizontalLineCounter,
Value = cell,
VerticalLineIndex = verticalLineCounter
};
Cells.Add(matrixCell);
if (Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).Count() == 0)
{
var line = new MatrixLine()
{
LineType = Line.Vertical,
LineIndex = verticalLineCounter
};
Lines.Add(line);
}
Lines.Where(line => line.LineType == Line.Vertical && line.LineIndex == verticalLineCounter).FirstOrDefault().Cells.Add(matrixCell);
if (Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).Count() == 0)
{
var line = new MatrixLine()
{
LineType = Line.Horizontal,
LineIndex = horizontalLineCounter
};
Lines.Add(line);
}
Lines.Where(line => line.LineType == Line.Horizontal && line.LineIndex == horizontalLineCounter).FirstOrDefault().Cells.Add(matrixCell);
verticalLineCounter++;
}
horizontalLineCounter++;
}
}
}
class MatrixCell
{
public int Value { get; set; }
public int VerticalLineIndex { get; set; }
public int HorizontalLineIndex { get; set; }
}
class MatrixLine
{
public Line LineType { get; set; }
public int LineIndex { get; set; }
public List<MatrixCell> Cells { get; set; }
public MatrixLine()
{
Cells = new List<MatrixCell>();
}
}
enum Line
{
Horizontal,
Vertical
}
private static void Search(Matrix matrix, bool optimizeCellCount, out IEnumerable<MatrixCell> optimizedSelection, out int iterations)
{
optimizedSelection = null;
var count = 0;
iterations = 0;
for (int i = 0; i < matrix.Width; i++)
{
for (int j = 1; j <= matrix.Width; j++)
{
var selectedVerticalLines = matrix.Lines.Where(line => line.LineType == Line.Vertical).Skip(i).Take(j);
for (int k = 0; k < matrix.Height; k++)
{
for (int l = 1; l <= matrix.Height; l++)
{
/**
* Here's where the search is optimized
**********************************************************************************************
*/
if (optimizeCellCount)
{
//if the submatrix cell count is smaller than the current count, break the iteration
if (count > Math.Min(Math.Abs(matrix.Height - k), l) * Math.Min(Math.Abs(matrix.Height - i), j))
{
continue;
}
}
/*
**********************************************************************************************
*/
iterations++;
var selectedHorizontalLines = matrix.Lines.Where(line => line.LineType == Line.Horizontal).Skip(k).Take(l);
var horizontalCells = selectedHorizontalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) =>
{
a.AddRange(b.Cells);
return a;
});
var verticalCells = selectedVerticalLines.Aggregate<MatrixLine, List<MatrixCell>>(new List<MatrixCell>(), (a, b) =>
{
a.AddRange(b.Cells);
return a;
});
var cells = horizontalCells.Intersect(verticalCells);
if (cells.Count() > count)
{
var sum = cells.Sum(t => t.Value);
var cellsCount = cells.Count();
if (sum != 0)
{
if (cellsCount/(double)sum == 2)
{
//match
optimizedSelection = cells;
count = cellsCount;
}
}
}
}
}
}
}
}
private static float GetLineCost(int width, int startPosition, int length)
{
float cost = 0;
for (int i = startPosition; i < length; i++)
{
cost += Math.Min(Math.Abs(width - i), i + 1);
}
return cost;
}
static void Main(string[] args)
{
Matrix matrix = new Matrix(20, 1);
bool optimizeCellCount = true;
IEnumerable<MatrixCell> optimizedSelection;
int iterations;
var watch = new System.Diagnostics.Stopwatch();
//optimized search
watch.Start();
Search(matrix, optimizeCellCount, out optimizedSelection, out iterations);
watch.Stop();
Console.WriteLine("Full Optimized Search");
Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}",
optimizedSelection.Min(cell => cell.VerticalLineIndex),
optimizedSelection.Min(cell => cell.HorizontalLineIndex),
optimizedSelection.Max(cell => cell.VerticalLineIndex),
optimizedSelection.Max(cell => cell.HorizontalLineIndex),
optimizedSelection.Count(),
watch.Elapsed,
iterations
);
watch.Reset();
//no optimization
watch.Start();
Search(matrix, !optimizeCellCount, out optimizedSelection, out iterations);
watch.Stop();
Console.WriteLine("Non-Optimized Search");
Console.WriteLine("position: [{0},{1}],[{2},{3}] size : {4} search time : {5} iterations: {6}",
optimizedSelection.Min(cell => cell.VerticalLineIndex),
optimizedSelection.Min(cell => cell.HorizontalLineIndex),
optimizedSelection.Max(cell => cell.VerticalLineIndex),
optimizedSelection.Max(cell => cell.HorizontalLineIndex),
optimizedSelection.Count(),
watch.Elapsed,
iterations
);
watch.Reset();
//Console Output:
/***************************************************************************************
* Full Optimized Search
* position: [9,1],[18,19] size : 190 search time : 00:00:02.3963657 iterations: 19108
* Non-Optimized Search
* position: [9,1],[18,19] size : 190 search time : 00:00:05.8385388 iterations: 160000
****************************************************************************************/
}
}
एक submatrix क्या है? –