Эффективный способ сравнения строк версий в Java
Возможный дубликат:
Как вы сравниваете две версии строк в Java?
У меня есть 2 строки, которые содержат информацию о версии, как показано ниже:
str1 = "1.2"
str2 = "1.1.2"
Теперь любой может сказать мне эффективный способ сравнить эти версии внутри строк в Java и вернуть 0, если они равны, -1, если str1
10 ответов
Требуется commons-lang3-3.8.1.jar для строковых операций.
/**
* Compares two version strings.
*
* Use this instead of String.compareTo() for a non-lexicographical
* comparison that works for version strings. e.g. "1.10".compareTo("1.6").
*
* @param v1 a string of alpha numerals separated by decimal points.
* @param v2 a string of alpha numerals separated by decimal points.
* @return The result is 1 if v1 is greater than v2.
* The result is 2 if v2 is greater than v1.
* The result is -1 if the version format is unrecognized.
* The result is zero if the strings are equal.
*/
public int VersionCompare(String v1,String v2)
{
int v1Len=StringUtils.countMatches(v1,".");
int v2Len=StringUtils.countMatches(v2,".");
if(v1Len!=v2Len)
{
int count=Math.abs(v1Len-v2Len);
if(v1Len>v2Len)
for(int i=1;i<=count;i++)
v2+=".0";
else
for(int i=1;i<=count;i++)
v1+=".0";
}
if(v1.equals(v2))
return 0;
String[] v1Str=StringUtils.split(v1, ".");
String[] v2Str=StringUtils.split(v2, ".");
for(int i=0;i<v1Str.length;i++)
{
String str1="",str2="";
for (char c : v1Str[i].toCharArray()) {
if(Character.isLetter(c))
{
int u=c-'a'+1;
if(u<10)
str1+=String.valueOf("0"+u);
else
str1+=String.valueOf(u);
}
else
str1+=String.valueOf(c);
}
for (char c : v2Str[i].toCharArray()) {
if(Character.isLetter(c))
{
int u=c-'a'+1;
if(u<10)
str2+=String.valueOf("0"+u);
else
str2+=String.valueOf(u);
}
else
str2+=String.valueOf(c);
}
v1Str[i]="1"+str1;
v2Str[i]="1"+str2;
int num1=Integer.parseInt(v1Str[i]);
int num2=Integer.parseInt(v2Str[i]);
if(num1!=num2)
{
if(num1>num2)
return 1;
else
return 2;
}
}
return -1;
}
Как уже отмечали другие, String.split() - это очень простой способ выполнить желаемое сравнение, и Майк Дек замечает, что с такими (вероятными) короткими строками это, вероятно, не будет иметь большого значения, но что Привет! Если вы хотите выполнить сравнение без анализа строки вручную и иметь возможность завершить работу раньше, вы можете попробовать класс java.util.Scanner.
public static int versionCompare(String str1, String str2) {
try ( Scanner s1 = new Scanner(str1);
Scanner s2 = new Scanner(str2);) {
s1.useDelimiter("\\.");
s2.useDelimiter("\\.");
while (s1.hasNextInt() && s2.hasNextInt()) {
int v1 = s1.nextInt();
int v2 = s2.nextInt();
if (v1 < v2) {
return -1;
} else if (v1 > v2) {
return 1;
}
}
if (s1.hasNextInt() && s1.nextInt() != 0)
return 1; //str1 has an additional lower-level version number
if (s2.hasNextInt() && s2.nextInt() != 0)
return -1; //str2 has an additional lower-level version
return 0;
} // end of try-with-resources
}
Это почти наверняка не самый эффективный способ сделать это, но учитывая, что строки номера версии почти всегда будут состоять всего из нескольких символов, я не думаю, что стоит оптимизировать дальше:
public static int compareVersions(String v1, String v2) {
String[] components1 = v1.split("\\.");
String[] components2 = v2.split("\\.");
int length = Math.min(components1.length, components2.length);
for(int i = 0; i < length; i++) {
int result = new Integer(components1[i]).compareTo(Integer.parseInt(components2[i]));
if(result != 0) {
return result;
}
}
return Integer.compare(components1.length, components2.length);
}
Я хотел сделать это сам, и я вижу три разных подхода к этому, и до сих пор почти все разделяют строки версий. Я не считаю это эффективным, хотя по размеру кода он хорошо читается и выглядит хорошо.
подходы:
- Предположим, что верхний предел количества секций (порядковых номеров) в строке версии, а также ограничение на значение, представленное там. Часто максимум 4 точки и максимум 999 для любого порядкового номера. Вы можете видеть, куда это идет, и это идет к преобразованию версии, чтобы уместиться в строку как: "1.0" => "001000000000" с форматом строки или некоторым другим способом дополнить каждый порядковый номер. Затем сделайте сравнение строк.
- Разбейте строки по порядковому разделителю ('.'), Итерируйте их и сравните проанализированную версию. Этот подход хорошо продемонстрировал Алекс Гительман.
- Сравнение ординалов по мере того, как вы разбираете их из рассматриваемых строк версий. Если бы все строки были просто указателями на массивы символов, как в C, то это был бы понятный подход (где вы бы заменили символ '.' На нулевой терминатор, как он был найден, и переместили бы 2 или 4 указателя вокруг.
Мысли о трех подходах:
- Была ссылка в блоге, которая показывала, как работать с 1. Ограничения - длина строки версии, количество разделов и максимальное значение раздела. Я не думаю, что это безумие - иметь такую строку, которая в один момент ломает 10000. Кроме того, большинство реализаций по-прежнему разбивают строку.
- Разделение строк заранее понятно для чтения и размышления, но мы проходим каждую строку примерно дважды, чтобы сделать это. Я хотел бы сравнить, как это время со следующим подходом.
- Сравнивая строку при ее разбиении, вы получаете преимущество, заключающееся в том, что вы можете прекратить расщепление очень рано при сравнении: "2.1001.100101.9999998" с "1.0.0.0.0.0.1.0.0.0.1". Если бы это был C, а не Java, преимущества могли бы продолжаться, чтобы ограничить объем памяти, выделяемой для новых строк для каждого раздела каждой версии, но это не так.
Я не видел, чтобы кто-то приводил пример этого третьего подхода, поэтому я хотел бы добавить его здесь в качестве ответа на вопрос эффективности.
public class VersionHelper {
/**
* Compares one version string to another version string by dotted ordinals.
* eg. "1.0" > "0.09" ; "0.9.5" < "0.10",
* also "1.0" < "1.0.0" but "1.0" == "01.00"
*
* @param left the left hand version string
* @param right the right hand version string
* @return 0 if equal, -1 if thisVersion < comparedVersion and 1 otherwise.
*/
public static int compare(@NotNull String left, @NotNull String right) {
if (left.equals(right)) {
return 0;
}
int leftStart = 0, rightStart = 0, result;
do {
int leftEnd = left.indexOf('.', leftStart);
int rightEnd = right.indexOf('.', rightStart);
Integer leftValue = Integer.parseInt(leftEnd < 0
? left.substring(leftStart)
: left.substring(leftStart, leftEnd));
Integer rightValue = Integer.parseInt(rightEnd < 0
? right.substring(rightStart)
: right.substring(rightStart, rightEnd));
result = leftValue.compareTo(rightValue);
leftStart = leftEnd + 1;
rightStart = rightEnd + 1;
} while (result == 0 && leftStart > 0 && rightStart > 0);
if (result == 0) {
if (leftStart > rightStart) {
return containsNonZeroValue(left, leftStart) ? 1 : 0;
}
if (leftStart < rightStart) {
return containsNonZeroValue(right, rightStart) ? -1 : 0;
}
}
return result;
}
private static boolean containsNonZeroValue(String str, int beginIndex) {
for (int i = beginIndex; i < str.length(); i++) {
char c = str.charAt(i);
if (c != '0' && c != '.') {
return true;
}
}
return false;
}
}
Модульный тест, демонстрирующий ожидаемый результат.
public class VersionHelperTest {
@Test
public void testCompare() throws Exception {
assertEquals(1, VersionHelper.compare("1", "0.9"));
assertEquals(1, VersionHelper.compare("0.0.0.2", "0.0.0.1"));
assertEquals(1, VersionHelper.compare("1.0", "0.9"));
assertEquals(1, VersionHelper.compare("2.0.1", "2.0.0"));
assertEquals(1, VersionHelper.compare("2.0.1", "2.0"));
assertEquals(1, VersionHelper.compare("2.0.1", "2"));
assertEquals(1, VersionHelper.compare("0.9.1", "0.9.0"));
assertEquals(1, VersionHelper.compare("0.9.2", "0.9.1"));
assertEquals(1, VersionHelper.compare("0.9.11", "0.9.2"));
assertEquals(1, VersionHelper.compare("0.9.12", "0.9.11"));
assertEquals(1, VersionHelper.compare("0.10", "0.9"));
assertEquals(0, VersionHelper.compare("0.10", "0.10"));
assertEquals(-1, VersionHelper.compare("2.10", "2.10.1"));
assertEquals(-1, VersionHelper.compare("0.0.0.2", "0.1"));
assertEquals(1, VersionHelper.compare("1.0", "0.9.2"));
assertEquals(1, VersionHelper.compare("1.10", "1.6"));
assertEquals(0, VersionHelper.compare("1.10", "1.10.0.0.0.0"));
assertEquals(1, VersionHelper.compare("1.10.0.0.0.1", "1.10"));
assertEquals(0, VersionHelper.compare("1.10.0.0.0.0", "1.10"));
assertEquals(1, VersionHelper.compare("1.10.0.0.0.1", "1.10"));
}
}
Сравнение строк версий может привести к путанице; вы получаете бесполезные ответы, потому что единственный способ сделать эту работу - быть очень точным в том, что такое ваше соглашение о заказе. Я видел одну сравнительно короткую и полную функцию сравнения версий в блоге с кодом, размещенным в открытом доступе - он не на Java, но должно быть просто увидеть, как это адаптировать.
Адаптировано из ответа Алекса Гительмана.
int compareVersions( String str1, String str2 ){
if( str1.equals(str2) ) return 0; // Short circuit when you shoot for efficiency
String[] vals1 = str1.split("\\.");
String[] vals2 = str2.split("\\.");
int i=0;
// Most efficient way to skip past equal version subparts
while( i<vals1.length && i<val2.length && vals[i].equals(vals[i]) ) i++;
// If we didn't reach the end,
if( i<vals1.length && i<val2.length )
// have to use integer comparison to avoid the "10"<"1" problem
return Integer.valueOf(vals1[i]).compareTo( Integer.valueOf(vals2[i]) );
if( i<vals1.length ){ // end of str2, check if str1 is all 0's
boolean allZeros = true;
for( int j = i; allZeros & (j < vals1.length); j++ )
allZeros &= ( Integer.parseInt( vals1[j] ) == 0 );
return allZeros ? 0 : -1;
}
if( i<vals2.length ){ // end of str1, check if str2 is all 0's
boolean allZeros = true;
for( int j = i; allZeros & (j < vals2.length); j++ )
allZeros &= ( Integer.parseInt( vals2[j] ) == 0 );
return allZeros ? 0 : 1;
}
return 0; // Should never happen (identical strings.)
}
Так что, как видите, не так тривиально. Также это не удается, если вы разрешаете ввод 0, но я никогда не видел версию "1.04.5" или w/e. Вам нужно будет использовать целочисленное сравнение в цикле while, чтобы это исправить. Это становится еще сложнее, когда вы смешиваете буквы с числами в строках версий.
Разделить строку на "." или каким бы ни был ваш разделитель, затем проанализируйте каждый из этих токенов со значением Integer и сравните.
int compareStringIntegerValue(String s1, String s2, String delimeter)
{
String[] s1Tokens = s1.split(delimeter);
String[] s2Tokens = s2.split(delimeter);
int returnValue = 0;
if(s1Tokens.length > s2Tokens.length)
{
for(int i = 0; i<s1Tokens.length; i++)
{
int s1Value = Integer.parseString(s1Tokens[i]);
int s2Value = Integer.parseString(s2Tokens[i]);
Integer s1Integer = new Integer(s1Value);
Integer s2Integer = new Integer(s2Value);
returnValue = s1Integer.compareTo(s2Value);
if( 0 == isEqual)
{
continue;
}
return returnValue; //end execution
}
return returnValue; //values are equal
}
Я оставлю другое заявление в качестве упражнения.
Разделите их на массивы, а затем сравните.
// check if two strings are equal. If they are return 0;
String[] a1;
String[] a2;
int i = 0;
while (true) {
if (i == a1.length && i < a2.length) return -1;
else if (i < a1.length && i == a2.length) return 1;
if (a1[i].equals(a2[i]) {
i++;
continue;
}
return a1[i].compareTo(a2[i];
}
return 0;
Я бы разделил проблему на две части: форматирование и сравнение. Если вы можете предположить, что формат правильный, то сравнение только номера версии очень просто:
final int versionA = Integer.parseInt( "01.02.00".replaceAll( "\\.", "" ) );
final int versionB = Integer.parseInt( "01.12.00".replaceAll( "\\.", "" ) );
Тогда обе версии можно сравнить как целые числа. Таким образом, "большая проблема" - это формат, но в нем может быть много правил. В моем случае я просто заполняю как минимум две пары цифр, поэтому формат всегда равен "99.99.99", а затем я выполняю приведенное выше преобразование; так что в моем случае логика программы заключается в форматировании, а не в сравнении версий. Теперь, если вы делаете что-то очень конкретное и, возможно, вы можете доверять источнику строки версии, возможно, вы просто можете проверить длину строки версии, а затем просто выполнить преобразование int... но я думаю, что это лучший способ убедитесь, что формат соответствует ожидаемому.
Шаг 1: Используйте StringTokenizer в Java с точкой в качестве разделителя
StringTokenizer(String str, String delimiters) или же
Ты можешь использовать String.split() а также Pattern.split(), разделить на точку, а затем преобразовать каждую строку в целое число, используя Integer.parseInt(String str)
Шаг 2: Сравните целое число слева направо.