開発中に発生したブレーク番号の最小値に基づいて新しい文書アルゴリズムを挿入
今のこの製品を作るとき、よくある文書挿入シーンに遭遇しました.
シーンの説明は次のとおりです.
工場内の文書の一種で、この文書の単号(単号は文字列タイプ)の生成には以下の制限条件が必要である.
挿入するときは順番に挿入します.つまり、単号はインクリメント1になります.作業者が操作する場合、文書の削除に遭遇した場合は、ランダムに削除されます.
この場合、新しい文書を挿入し続けると、新しい文書番号が満たされる条件は、単一番号シーケンス全体の最小連続完全シーケンスの最大単一番号に1を加算することです.
たとえば、元の番号のシーケンスは、1,2,3,4,5,6,7です.
(1)単号が4の文書をランダムに削除し,このときのシーケンス番号は1,2,3,5,6,7であり,このときに新しい文書を挿入すると最小完連続整シーケンスは(1,2,3),新規単号は4である.
(2)3,5,7をランダムに削除し、このときのシリアル番号は1,2,4,6であり、このとき新しい文書を挿入する場合、シングル番号は残りのシングル番号の最小連続完全シーケンス(1,2)であり、新規シングル番号は3である.
問題は実は簡単です.
<1>もちろん小規模なデータであれば,最小のブレーク番号までループで直接スキャンできる.
コードは次のとおりです.
<2>私たちのこの製品は製造業にサービスしているので、中に含まれている文書の数が大きいかもしれません.性能の観点から、この場所は複雑さを低減するために良いアルゴリズムを設計することができます.本人がまず考えた変は二分ルックアップ法で、二分ルックアップ法の派生アルゴリズムを利用して、断番の中の一番小さいサイズをすぐに見つけることができて、この時挿入する必要がある新しい単号は簡単に算出することができます.
疑似コードは次のとおりです.
int max=20;
Array[] arr = new Array[max];
int left = 0;right = max-1;
while(left <= right){
int midd = (left+right)/2;
if(arr[midd]==midd+1){
left = midd+1;
continue;
}else if(arr[midd]==null || arr[midd] != midd+1){
right = midd -1;
continue;
}
}
return right+1;
具体的なC#コード:
このアルゴリズムは基本的に生産で出会った同じ問題を解決できると信じていますが、もっと簡単な、コードを必要としない方法はありますか?コードを必要とせず、SQLだけで済む3つ目の解決策を以下に示します.
<3>テーブル構造が与えられる.表A、フィールドA_が1つのみID、ncharタイプ.A_IDは不連続リフトシーケンスです.
上記のSQLを使って、必要な単号を直接求めることができます!
以上は私のためにこの问题の少しの心得に出会って、また各位がよろしくお愿いします~
シーンの説明は次のとおりです.
工場内の文書の一種で、この文書の単号(単号は文字列タイプ)の生成には以下の制限条件が必要である.
挿入するときは順番に挿入します.つまり、単号はインクリメント1になります.作業者が操作する場合、文書の削除に遭遇した場合は、ランダムに削除されます.
この場合、新しい文書を挿入し続けると、新しい文書番号が満たされる条件は、単一番号シーケンス全体の最小連続完全シーケンスの最大単一番号に1を加算することです.
たとえば、元の番号のシーケンスは、1,2,3,4,5,6,7です.
(1)単号が4の文書をランダムに削除し,このときのシーケンス番号は1,2,3,5,6,7であり,このときに新しい文書を挿入すると最小完連続整シーケンスは(1,2,3),新規単号は4である.
(2)3,5,7をランダムに削除し、このときのシリアル番号は1,2,4,6であり、このとき新しい文書を挿入する場合、シングル番号は残りのシングル番号の最小連続完全シーケンス(1,2)であり、新規シングル番号は3である.
問題は実は簡単です.
<1>もちろん小規模なデータであれば,最小のブレーク番号までループで直接スキャンできる.
コードは次のとおりです.
int minLackNum;
if (reslut.Count != max)
{
for (int i = 0; i < reslut.Count; i++)
{
if (Convert.ToInt16(reslut[i][0], CultureInfo.CurrentCulture) != i + 1)
{minLackNum = i; break;
}
}
}
<2>私たちのこの製品は製造業にサービスしているので、中に含まれている文書の数が大きいかもしれません.性能の観点から、この場所は複雑さを低減するために良いアルゴリズムを設計することができます.本人がまず考えた変は二分ルックアップ法で、二分ルックアップ法の派生アルゴリズムを利用して、断番の中の一番小さいサイズをすぐに見つけることができて、この時挿入する必要がある新しい単号は簡単に算出することができます.
疑似コードは次のとおりです.
int max=20;
Array[] arr = new Array[max];
int left = 0;right = max-1;
while(left <= right){
int midd = (left+right)/2;
if(arr[midd]==midd+1){
left = midd+1;
continue;
}else if(arr[midd]==null || arr[midd] != midd+1){
right = midd -1;
continue;
}
}
return right+1;
具体的なC#コード:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int[] arr = new int[] {1,2,3,4,5,6,7,9,10,11,12};
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
Console.WriteLine("*");
int midd = (left + right) / 2;
if (arr[midd] == midd + 1)
{
left = midd + 1;
continue;
}
else if (arr[midd] != midd + 1)
{
right = midd - 1;
continue;
}
Console.WriteLine("*");
}
Console.Write(right + 2);
Console.ReadKey();
}
}
}
このアルゴリズムは基本的に生産で出会った同じ問題を解決できると信じていますが、もっと簡単な、コードを必要としない方法はありますか?コードを必要とせず、SQLだけで済む3つ目の解決策を以下に示します.
<3>テーブル構造が与えられる.表A、フィールドA_が1つのみID、ncharタイプ.A_IDは不連続リフトシーケンスです.
Select MIN(A_NID) from (Select CAST(A_ID AS Int)+1 as A_NID from A) as B where A_NID not in (select A_ID from A);
上記のSQLを使って、必要な単号を直接求めることができます!
以上は私のためにこの问题の少しの心得に出会って、また各位がよろしくお愿いします~