간격리스트가 있다고 가정하십시오 : [1, 90], [104, 234], [235, 300], .... 모든 간격의 이름은 A1, B, B1, ...입니다. 주어진 값으로 나는 간격의 이름을 원한다. (112 -> B, 100 -> special_value). 가장 좋고 빠른 implentation은 무엇입니까? if/else if 목록보다 나은 것.값과의 간격을 찾으십시오.
간격은 순서대로 정렬되며 겹침이 없습니다. 입력 값은 많지만 간격은 한 세트뿐입니다. 크기 간격은 매우 다르며, 일부는 매우 작고, 다른 것은 매우 큽니다.
아이디어 : 간격의 시작 값에 대한 맵 객체를 만듭니다. 가능한 간격을 찾았 으면 값이 간격에 있는지 확인하십시오.
class MyInterval
{
public:
MyInterval(double begin, double end)
: m_begin(begin), m_end(end)
{
};
double m_begin, m_end;
};
bool operator < ( const MyInterval& left, const MyInterval& right)
{
return (left.m_begin < right.m_begin);
}
std::map<MyInterval,std::string> store;
// use upper_bound to get the place+1 and then you could check the interval
std::map<MyInterval,std::string>::iterator iter = store.upper_bound(MyInterval(value,value));
if (iter != store.begin())
{
--iter;
if (iter->first.m_end >= value)
{
std::string result_text = iter->second;
// Here is your result
}
}
자세한 정보 : link.
Visual Studio 2010에서 테스트되었습니다.
값이 어떤 간격에도 속하지 않으면 어떻게됩니까? –
그러면'iter'는'store.end()'를 가리킬 것입니다 – wilhelmtell
정말입니까? 내 예에서 나는 100을 가치로 사용합니까? –
else if 시퀀스의 가장 간단한 개선은 간격의 연결된 목록 (또는 배열)을 만들고 그 위에 반복하는 것입니다. 이것은 매우 단순한 조언처럼 보입니다. 그래서 당신의 질문에 답해주기를 바랍니다.
예를 들어, 간격이 순서대로 정렬되고 겹침이없는 것처럼 보입니다. 그래도 틈이 생길 수 있습니다.
어떤 종류의 반복이라도 O (N) 솔루션을 얻을 수 있습니다. 값을 저장할 수있는 간격에 대한 이진 검색을 수행하면 반복을 향상시킬 수 있습니다.
간격을 지정 했습니까? 간격을 공통 부분으로합니까? – Naszta
주문 됨, 중복 없음 –
귀하의 간격 중 가장 큰 가치는 무엇입니까? – Xeo