Реализуйте двоичный поиск в объектах
C-массивы на самом деле не являются массивами во время выполнения, где они просто являются указателями на непрерывный блок объектов одного типа. Когда вы видите items[n], это просто синтаксический сахар для *(items+n).
В вашем примере addLines[1] будет *(lines+1), а addLines[0] будет *(lines+0), то есть *lines. Итак, addLines просто lines без разыменования указателя. *lines - это первый элемент в массиве, а lines - весь массив.
Массивы имеют некоторые отличия от указателей во время компиляции. Например, sizeof(addLines) даст вам размер всего массива.
Массив теряется, как только вы передаете массив где-нибудь, где его размер может быть переменным, но вы все равно можете использовать оператор индекса. Например:
#include <Foundation/Foundation.h>
#define showsize( expr ) ( printf(#expr " = %zd\n", ( expr ) ) )
CGPoint *
pass_back(CGPoint points[4])
{
showsize(sizeof(points));
return points;
}
int
main(void)
{
CGPoint square[] = {CGPointMake(-1.0, 1.0),
CGPointMake( 1.0, 1.0),
CGPointMake( 1.0, -1.0),
CGPointMake(-1.0, -1.0)};
CGPoint* returned;
int i;
showsize(sizeof(CGPoint));
showsize(sizeof(CGPoint*));
showsize(sizeof(square));
returned = pass_back(square);
showsize(sizeof(returned));
for (i = 0; i < 4; ++i) {
printf("returned[%d] = {%0.1f, %0.1f}\n", i, (float) returned[i].x,
(float) returned[i].y);
}
return 0;
}
Это выводит следующее на моем Mac:
sizeof(CGPoint) = 8
sizeof(CGPoint*) = 4
sizeof(square) = 32
sizeof(points) = 4
sizeof(returned) = 4
returned[0] = {-1.0, 1.0}
returned[1] = {1.0, 1.0}
returned[2] = {1.0, -1.0}
returned[3] = {-1.0, -1.0}
Здесь, square - размер четырех CGPoint с, но один раз отправляется на pass_back, это всего лишь размер указателя, потому что это так. Когда указатель возвращается (и называется returned), он все еще может использоваться как массив.
Обратите внимание на магическое число 4 в цикле. Указатель не знает длину массива, на который он указывает.
Массивы нельзя переназначить с помощью оператора =. Если вы действительно должны заполнить addLines точками из lines, вы можете сделать это с помощью чего-то вроде следующего:
memcpy(addLines, lines, sizeof(CGPoint) * numberOfPoints);
Вы должны будете получить numberOfPoints откуда-то и addLines ] должно быть достаточно большим, чтобы справиться с этими вопросами. Это нормально, если число точек является константой, но было бы плохо , если количество точек может изменяться во время выполнения, особенно если точки приходят из внешнего мира (подумайте о выполнении произвольного кода).
Я бы изменил averageResponseTimePoints так, чтобы он возвращал NSArray, а не массив в стиле C. Вам нужно будет инкапсулировать CGPoint в объекты - либо свой собственный объект, либо NSValue.
Вот пример того, как вы могли бы написать averageResponseTimePoints:
- (NSArray*) averageResponseTimePoints
{
NSMutableArray* result = [[[NSMutableArray alloc] init] autorelease];
for (int i = 0; i < numberOfPoints; ++i) {
NSValue* point = [NSValue value:points+i
withObjCType:@encode(CGPoint)];
[result addObject:point];
}
return result;
}
Если ваш код работает с CocoaTouch, вы можете использовать его для создания значения точки вместо:
NSValue* point = [NSValue valueWithCGPoint:points[i]];
Чтобы вывести CGPoint из массива, вы можете написать что-то вроде этого:
for (NSValue* value in result) {
NSPoint pt;
[value getValue:&pt];
NSLog(@"%f %f", pt.x, pt.y);
}
Или с CocoaTouch:
CGPoint pt = [value CGPointValue];
3 ответа
В статье Упорядочивание объектов учебников по Java есть пример написания собственного Comparator для выполнения сравнений с пользовательскими типами.
Затем ArrayList (или любой другой List ), ключ для поиска вместе с Comparator можно передать в Collections.binarySearch ].
Вот пример:
import java.util.*;
class BinarySearchWithComparator
{
public static void main(String[] args)
{
// Please scroll down to see 'User' class implementation.
List<User> l = new ArrayList<User>();
l.add(new User(10, "A"));
l.add(new User(20, "B"));
l.add(new User(30, "C"));
Comparator<User> c = new Comparator<User>() {
public int compare(User u1, User u2) {
return u1.getId().compareTo(u2.getId());
}
};
// Must pass in an object of type 'User' as the key.
// The key is an 'User' with the 'id' which is been searched for.
// The 'name' field is not used in the comparison for the binary search,
// so it can be a dummy value -- here it is omitted with a null.
//
// Also note that the List must be sorted before running binarySearch,
// in this case, the list is already sorted.
int index = Collections.binarySearch(l, new User(20, null), c);
System.out.println(index); // Output: 1
index = Collections.binarySearch(l, new User(10, null), c);
System.out.println(index); // Output: 0
index = Collections.binarySearch(l, new User(42, null), c);
System.out.println(index); // Output: -4
// See javadoc for meaning of return value.
}
}
class User {
private int id;
private String name;
public User(int id, String name) {
this.id = id;
this.name = name;
}
public Integer getId() {
return Integer.valueOf(id);
}
}
import java.util.Collections;
Collections.binarySearch(users, id);